백준 1780 : 종이의 개수

https://www.acmicpc.net/problem/1780

1. 접근

• 분할 정복에서는 큰 문제를 작게 분할하면서 문제를 해결하는데, 이 문제의 경우 문제에서 이미 분할하는 방법을 정의하고 있다. 이에 따라서 코드를 짜기만 하면 된다.
• 99 에서 33 1*1 로 점점 크기를 줄여나가고, 종이의 시작점을 변경시켜주면 된다.
• 2차원 배열을 사용하게되어 O(N^3) 쯤 되면 시간초과가 날 줄 알았지만 n의 크기가 작아 시간초과는 나지 않았다.

2. 나의 풀이

#include <iostream>
#define MAX 2200
using namespace std;

int n;
int answer[3];
int paper[MAX][MAX];

bool check(int x,int y,int size) {
	int start = paper[x][y];
	for (int i = x; i < x+size; i++) {
		for (int j = y; j < y+size; j++) {
			if (start != paper[i][j]) return false;
		}
	}
	return true;
}

void divide(int x, int y, int size) {
	if (check(x, y, size)) {
		answer[paper[x][y] + 1]++;
	}
	else {
		int nextsize = size / 3;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				divide(x + nextsize * i, y + nextsize * j, nextsize);
			}
		}
	}
}

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

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

	divide(0, 0, n);
	cout << answer[0] << "\n";
	cout << answer[1] << "\n";
	cout << answer[2] << "\n";
}

3. 참고

https://chanhuiseok.github.io/posts/baek-13/
분할정복으로 잘 설명한 블로그