[백준 1780] 종이의 개수

문제 링크 : https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

먼저 가장 큰 사각형이 사용할 수 있는 종이이면 사용하고

 

아닐 경우 9개의 작은 종이들로 나누어 다시 검사한다.

 

---

 

가장 큰 사각형의 변의 길이는 최악의 경우에 3^7이 들어온다. 

 

따라서 사용할 수 있는 종이인지 확인하는데 3^14만큼의 연산 횟수가 소요된다.

 

만약 사용할 수 없는 종이여서 작은 사각형 9개로 나눠어 검사해도 소요되는 총 연산은 마찬가지로 3^14이다.

 

$$3^{14} / 9 * 9$$

 

이런식으로 계산해 보면, 모든 종이가 한칸일 때만 사용할 수 있을 때 (최악의 경우)

 

1 0 1

0 1 0

1 0 1

 

총 7 * 3^14의 연산 횟수가 필요하다.

 

이는 33,480,783으로 시간초과를 내지 않는다.

 

따라서 이 문제는 완전탐색해도 해결할 수 있는 단순구현 문제이다.

 

---

 

재귀함수에서는 세가지 정보를 필요로 한다.

 

종이 시작 위치의 좌표 (i, j)와 변의 길이(s)

 

만약 이 종이가 사용할 수 없는 종이라면 분할되는 9개의 작은 종이에 대한 정보는 다음과 같다.

 

t = s/3

 

i, j, t

i, j+t, t

i, j+2*t, t

i+t, j, t

i+t, j+t, t

i+t, j+2*t, t

i+2*t, j, t

i+2*t, j+t, t

i+2*t, j+2*t, t

 

---

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

int arr[n_][n_];
int cnt[3];

void solve(int x, int y, int s) {
	int tmp = arr[x][y];

	bool chk = true;
	for (int i = 0; i < s; i++) {
		for (int j = 0; j < s; j++) {
			if (arr[x + i][y + j] != tmp)
				chk = false;
		}
	}

	if (chk) {
		cnt[tmp + 1]++;
	}
	else {
		int d = s / 3;
		solve(x, y, d);
		solve(x + d, y, d);
		solve(x + 2 * d, y, d);
		solve(x, y + d, d);
		solve(x + d, y + d, d);
		solve(x + 2 * d, y + d, d);
		solve(x, y + 2 * d, d);
		solve(x + d, y + 2 * d, d);
		solve(x + 2 * d, y + 2 * d, d);
	}
}

int main(void) {
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}

	solve(0, 0, n);
	for (int i = 0; i < 3; i++) {
		printf("%d\n", cnt[i]);
	}

	return 0;
}