99코딩

풀이

#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 <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;
}

문제

풀이

 모든 땅의 높이가 각각 0,1,2,...,254,255,256으로 맞춰지는 시간을 구하여 그 중 최소 시간과 최소 시간이 나올 때의 땅의 높이를 구해 출력하면 된다.

#include <iostream>
#include <vector>

using namespace std;

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

	int n, m, b;
	int board[501][501];
	int minTime = 0x7f7f7f7f;
	int maxH = -1;

	cin >> n >> m >> b;

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

	for (int height = 0; height <= 256; height++) {
		int removeBlock = 0, deployBlock = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int h = board[i][j] - height;
				if (h > 0) removeBlock += h;
				else if (h < 0) deployBlock -= h;
			}
		}

		if (removeBlock + b >= deployBlock) {
			int t = 2 * removeBlock + deployBlock;
			if (t <= minTime) {
				minTime = t;
				maxH = height;
			}
		}
	}

	cout << minTime << " " << maxH;

	return 0;
}