99코딩

문제 조건

• 벽의 길이는 n미터, 롤러의 길이는 m미터
• 롤러는 벽을 벗어날 수 없음
• section 배열 안에 들어있는 번호들이 최소의 횟수로 전부 칠해져야함
• 이미 칠해진 부분은 또 칠해질 수 있음

문제 풀이

어차피 이미 칠해진 부분은 또 칠할 수 있기 때문에 n은 무시하였다.

1. 어디까지 칠해졌는지 확인하기 위해 paintedArea라는 변수를 선언
2. paintedArea에는 칠해지지않은 section[i]에 롤러의 길이 - 1을 더함으로써 몇 번째 벽까지 칠했는지 저장 후 answer++
3. paintedArea가 그 다음 section[i]보다 크거나 같다면 이미 해당 구역까지는 칠해졌으므로 continue
4. paintedArea가 section[i]의 마지막 원소보다 크거나 같다면 다시 칠해야하는 구역을 전부 칠한 것이므로 break
5. answer 리턴

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    int sectionLength = section.size();
    int paintedArea = 0;
    
    for(int i = 0;;i++) {
        if(paintedArea >= section[sectionLength - 1]) break;
        if(paintedArea >= section[i]) continue;
        
        paintedArea = section[i] + m - 1;
        answer++;
    }
    
    return answer;
}

문제 조건

• name의 길이 = yearning의 길이
• 각 사진마다 사진에 포함된 인물의 그리움 점수를 합산하여 추억 점수를 구함

문제 풀이

1. name을 key로 yearning을 value로 가지는 자료구조 m 선언
2. 각 사진에 포함된 인물 이름을 통해 그리움 점수를 구하고 합산하여 answer에 삽입
3. 출력

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<string> name, vector<int> yearning, vector<vector<string>> photo) {
    vector<int> answer;
    map<string, int> m;
    
    int nameLength = name.size();
    int photoLength = photo.size();
    
    for(int i = 0; i < nameLength; i++)
        m[name[i]] = yearning[i];
    
    for(int i = 0; i < photoLength; i++) {
        int sum = 0;
        
        for(string element : photo[i]) {
            sum += m[element];
        }
        
        answer.push_back(sum);
    }
    
    return answer;
}

풀이

#include <iostream>
#include <queue>

using namespace std;

int n, m;
int arr[1001][1001];
bool isVisited[1001][1001];

int dirX[4] = { 0, 1, 0, -1 };
int dirY[4] = { 1, 0, -1, 0 };

queue<pair<int, int>> q;

void bfs() {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int curX = x + dirX[i];
            int curY = y + dirY[i];

            if (curX < 0 || curX >= n || curY < 0 || curY >= m) continue;
            if (!isVisited[curX][curY]) {
                arr[curX][curY] = arr[x][y] + 1;
                isVisited[curX][curY] = true;
                q.push({ curX, curY });
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 2) {
                arr[i][j] = 0;
                q.push({ i, j });
                isVisited[i][j] = true;
            }
            if (arr[i][j] == 0)
                isVisited[i][j] = true;
        }

    bfs();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!isVisited[i][j])
                cout << "-1 ";
            else
                cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

문제

풀이

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int n, sum;
int arr[500000];
double result;

int main() {
    cin >> n;

    if (n == 0)
    {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    float tmp = n * 0.15;
    tmp = round(tmp);
    
    sort(arr, arr + n);

    for (int i = tmp; i < n - tmp; i++)
        sum += arr[i]; 

    result = sum / (n - tmp * 2);
    result = round(result);

    cout << result << endl;

    return 0;
}

풀이

3x3으로 분할해야하는 조금 귀찮은 분할정복 문제이다.

#include <iostream>

using namespace std;

int countA = 0, countB = 0, countC = 0;
int paper[2188][2188];

void conquer(int y, int x, int size) {
	int num = paper[y][x];

	for (int i = y; i < y + size; i++) {
		for (int j = x; j < x + size; j++) {
			if (num != paper[i][j]) {
				conquer(y, x, size / 3);
				conquer(y + size / 3, x, size / 3);
				conquer(y + size * 2 / 3, x, size / 3);
				conquer(y, x + size / 3, size / 3);
				conquer(y + size / 3, x + size / 3, size / 3);
				conquer(y + size * 2 / 3, x + size / 3, size / 3);
				conquer(y, x + size * 2 / 3, size / 3);
				conquer(y + size / 3, x + size * 2 / 3, size / 3);
				conquer(y + size * 2 / 3, x + size * 2 / 3, size / 3);

				return;
			}
		}
	}

	if (num == -1) countA++;
	else if (num == 0) countB++;
	else countC++;

	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> paper[i][j];

	conquer(0, 0, n);

	cout << countA << '\n' << countB << '\n' << countC;

	return 0;
}

풀이

문제를 보면 알 수 있듯이 분할정복 관련 문제이다.

#include <iostream>

using namespace std;

#define MAX 128

int n;
int cntWhite = 0, cntBlue = 0;
int map[MAX][MAX];

void DevideAndConquer(int x, int y, int size) {
	int color = map[x][y];

	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (color != map[i][j]){
				DevideAndConquer(x, y, size / 2);
				DevideAndConquer(x, y + size / 2, size / 2);
				DevideAndConquer(x + size / 2, y, size / 2);
				DevideAndConquer(x + size / 2, y + size / 2, size / 2);

				return;
			}
		}
	}
	if (color)
		cntBlue++;
	else
		cntWhite++;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	DevideAndConquer(0, 0, n);
	cout << cntWhite << "\n" << cntBlue;

	return 0;
}

풀이

분할정복을 이용하는 문제이다.

#include <iostream>

using namespace std;

int n, row, column;
int answer = 0;

void ZFunc(int y, int x, int size) {
	if (y == row && x == column) {
		cout << answer;
		
		return;
	}

	if (row < y + size && row >= y && column < x + size && column >= x) {
		ZFunc(y, x, size / 2);
		ZFunc(y, x + size / 2, size / 2);
		ZFunc(y + size / 2, x, size / 2);
		ZFunc(y + size / 2, x + size / 2, size / 2);
	}
	else
		answer += size * size;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int size = 1;

	cin >> n >> row >> column;

	size <<= n;

	ZFunc(0, 0, size);

	return 0;
}

풀이

간단한 분할정복 문제이다.

#include <iostream>
#include <string>

using namespace std;

string str[64];

void conquer(int y, int x, int size) {
	char state = str[y][x];

	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
			if (state != str[i][j]) {
				cout << '(';
				conquer(y, x, size / 2);
				conquer(y, x + size / 2, size / 2);
				conquer(y + size / 2, x, size / 2);
				conquer(y + size / 2, x + size / 2, size / 2);
				cout << ')';

				return;
			}

	cout << state;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> str[i];

	conquer(0, 0, n);

	return 0;
}

풀이

문자열을 받은 뒤 해당 문자열에서 주어진 알파벳과 같은 문자를 세어 출력하면 되는 간단한 문제다.

#include <iostream>
#include <string>

using namespace std;

string str;

int main() {
	while (true) {
		int cnt = 0;
		getline(cin, str);

		if (str[0] == '#') break;

		if (str[0] >= 'A' && str[0] <= 'Z') {
			for (int i = 2; i < str.size(); i++) {
				if (str[i] == str[0]) cnt++;
				if (str[i] == str[0] + 32) cnt++;
			}
		}
		else {
			for (int i = 2; i < str.size(); i++) {
				if (str[i] == str[0]) cnt++;
				if (str[i] == str[0] - 32) cnt++;
			}
		}

		cout << str[0] << ' ' << cnt << '\n';
	}

	return 0;
}

문제

풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, cnt1, cnt2; //cnt1 = 단지 수, cnt2 = 단지 내 집의 수
string area[25];
vector<int> v;
bool isVisited[25][25];

int dirX[] = { 0, 1, 0, -1 };
int dirY[] = { 1, 0, -1, 0 };

void dfs(int y, int x) {
	isVisited[y][x] = true;
	cnt2++;

	for (int i = 0; i < 4; i++) {
		int curY = y + dirY[i];
		int curX = x + dirX[i];

		if (curX < 0 || curY >= n || curY <0 || curY >= n) continue;
		if (isVisited[curY][curX] == false && area[curY][curX] == '1')
			dfs(curY, curX);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> area[i];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (isVisited[i][j] == false && area[i][j] == '1') {
				cnt2 = 0;
				dfs(i, j);
				v.push_back(cnt2);
				cnt1++;
			}
		}
	}

	cout << cnt1 << '\n';

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << '\n';
	}

	return 0;
}