종이의 개수 (feat. 백준, 1780번)

종이의 개수
https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int ans1, ans2, ans3, arr[2187][2187];
void solution(register int x, register int y, register int n) {
	int tmp = 10, count = 0;
	for (register int i = 0, j; i < n; ++i)
		for (j = 0; j < n; ++j)
			if (tmp == 10)
				tmp = arr[x + i][y + j], ++count;
			else
				if (tmp == arr[x + i][y + j])
					++count;
				else
					break;
	if (tmp == -1 && count == n * n)
		++ans1;
	else if (tmp == 0 && count == n * n)
		++ans2;
	else if (tmp == 1 && count == n * n)
		++ans3;
	else {
		solution(x, y, n / 3), solution(x + n / 3, y, n / 3), solution(x + 2 * n / 3, y, n / 3);
		solution(x, y + n / 3, n / 3), solution(x + n / 3, y + n / 3, n / 3), solution(x + 2 * n / 3, y + n / 3, n / 3);
		solution(x, y + 2 * n / 3, n / 3), solution(x + n / 3, y + 2 * n / 3, n / 3), solution(x + 2 * n / 3, y + 2 * n / 3, n / 3);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < N; ++j)
			cin >> arr[i][j];
	ans1 = ans2 = ans3 = 0;
	solution(0, 0, N);
	cout << ans1 << "\n" << ans2 << "\n" << ans3;
	return 0;
}
// *&)*@*

1. 이전 '색종이 만들기' 문제와 유사한 방식입니다.
2. 다른점이 있다면 2배씩 줄여나가는 것이 아니라 3배씩 줄여나가고, 2개의 정답이 아닌 3개의 정답을 출력하는 차이만 있을 뿐입니다.
3. 따라서 이전 문제를 먼저 풀어보시길 권장합니다.

색종이 만들기 (feat. 백준, 2630번)