종이의 개수

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	35301	20969	15720	58.541%

문제

N×N크기의 행렬로 표현되는 종이가 있다.

종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다.

우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.

2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수,

1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 3⁷, N은 3^k 꼴)이 주어진다.

다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를,

셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

예제 입력 1

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

예제 출력 1

10
12
11

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: djm03178, hwankim123, upsk1
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 분할 정복
• 재귀

---

분할정복 문제

종이가 모두 같다면 카운트

아니면 9부분으로 나눈 후에 다시 확인

길이가 1 (3^0)이 될때 까지 해당 로직을 반복한다.

통과된 코드

#include <iostream>
#include <cmath>

using namespace std;

constexpr int MAX = 2187;

int map[MAX][MAX];

int N;

// 0 = 0 / 1 = 1 / -1 = 2
int result[3];

void ConquestDivison(int x, int y, int w)
{
	// 종이의 길이가 1(3^0) 이라면 해당 종이의 카운트를 증가시켜 줍니다.
	if (w == 0) { 
		if (map[x][y] == -1) result[2]++;
		else result[map[x][y]]++;
		return;
	}

	int number = map[x][y];
	int temp = pow(3, w);
	bool check = true;
	for (int i = 0; i < temp; i++) {
		for (int j = 0; j < temp; j++) {
			// 모든 부분이 서로 같은지 체크합니다.
			// 다르다면 빠져나가고 마킹해줍니다.
			if (number == map[x + i][y + j]) { continue; }
			else {
				check = false;
				break;
			}
		}
		if (!check) break;
	}

	if (check) { // 모든 부분이 같다면 해강 종이의 카운트를 올려줍니다.
		if (number == -1) result[2]++;
		else result[map[x][y]]++;
		return;
	}
	
	int temp2 = pow(3, w - 1);

	// 분할 정복 9등분
	ConquestDivison(x              , y              , w - 1);
	ConquestDivison(x              , y + temp2      , w - 1);
	ConquestDivison(x              , y + 2 * (temp2), w - 1);

	ConquestDivison(x + temp2	   , y				, w - 1);
	ConquestDivison(x + temp2	   , y + temp2		, w - 1);
	ConquestDivison(x + temp2	   , y + 2 * (temp2), w - 1);

	ConquestDivison(x + 2 * (temp2), y	            , w - 1);
	ConquestDivison(x + 2 * (temp2), y + temp2	    , w - 1);
	ConquestDivison(x + 2 * (temp2), y + 2 * (temp2), w - 1);
}


int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	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];
		}
	}

	// N이 3의 몇승인지 확인합니다.
	int k = 0;
	int temp = N;
	while (temp != 1) {
		temp /= 3;
		k++;
	}
	
	ConquestDivison(0, 0, k);

	cout << result[2] << "\n" << result[0] << "\n" << result[1];

	return 0;
}