[백준/C++] 1780번: 종이의 개수

문제

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

---

문제 요약

N × N 크기의 행렬로 표현되는 종이의 각 칸에 -1, 0, 1 중 하나가 적혀 있다.

 

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

 

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

2. 그렇지 않다면, 종이를 같은 크기의 종이 9개로 자르고, 각각 잘린 종이에 대해 (1) 과정을 반복한다.

 

-1, 0, 1 로만 채워진 종이의 개수를 출력한다.

---

코드

#include <iostream>

using namespace std;

int n;

int board[2200][2200];

int minus_cnt;
int zero_cnt;
int one_cnt;

void divi(int x, int y, int cnt) {
	int value = board[x][y];

	bool flag = true;

	// 해당 종이에 다른 숫자가 적혀 있는지 확인
	for (int i = 0; i < cnt; i++) {
		for (int j = 0; j < cnt; j++) {
			if (value != board[x + i][y + j]) {
				flag = false;
				break;
			}
		}
		if (!flag) break;
	}

	// 다른 숫자가 없다면,
	if (flag) {
		if (value == -1) minus_cnt++;
		else if (value == 0) zero_cnt++;
		else one_cnt++;
	}
	// 다른 숫자가 있다면,
	else {
		int div_cnt = cnt / 3;

		for (int i = x; i < x + cnt; i = i + div_cnt) {
			for (int j = y; j < y + cnt; j = j + div_cnt) {
				divi(i, j, div_cnt);
			}
		}
	}
}

int main() {
	// 입출력 단축
	ios_base::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 >> board[i][j];
		}
	}

	// 분할 정복
	divi(0, 0, n);
	
	// 출력
	cout << minus_cnt << "\n";
	cout << zero_cnt << "\n";
	cout << one_cnt << "\n";

	return 0;
}

---

코드 설명

1. 종이의 크기와 각 칸에 적힌 정보를 입력 받는다.

 

2. 분할 정복 알고리즘을 진행한다.

 

2 - 1. 해당 종이에 다른 숫자가 적혀 있는지 확인한다.

 

2 - 2. 다른 숫자가 적혀 있지 않다면, 개수를 센다.

 

2 - 3. 다른 숫자가 적혀 있다면, 9개의 정사각형으로 나누어 재귀를 진행한다.

 

3. ( -1, 0, 1) 로만 채워진 종이의 개수를 출력한다.

---

고찰

범위가 3의 7제곱까지 인데, board[2020][2020]으로 설정해서 틀렸다..

 

오류로도 범위 오류가 아니라 "틀렸습니다"가 나와서 찾는데 꽤 걸렸다. ㅜㅜ