종이의 개수 (boj.kr/1780)

종이의 개수 (boj.kr/1780)

 

문제 해설 및 주의사항

N x N 종이의 각칸에는 -1 0 1 이 저장되어 있다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고(divide), 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 

-1로 만 채워진 종이. 0으로만. 1로만 채워진 종이의 개수를 구해내자.

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 브루트 포스?

- N 의 최대 크기는 3^7 = 2,187개 이다. 정사각형 최대 크기는 4,782,969.

전체 정사각형에서, 종이에 써있는 수가 같은 수 임을 알기 위해 반복하는 최대 갯수는

N / 9 * 9 (1번째 분할) + N / 81 * 9 (2번째 분할)... 이므로, 브루트 포스가 가능하다.

2. 과정

- 9개로 나눔(분할)

- 현재 재귀에서의 구간에서 종이가 기저사례인지 아닌지 확인 (check)

3. 구간의 설정

- 9등분 하는 것을 어떻게 표현할 것인가가 이 문제의 관건이다. 일일히 vector<<vector<int>> 참조자를 써가며 9등분 하는 방법도 있지만, 다른 방법을 사용했다.

- (int y, int x, int width) = ( 현재 y 좌표, 현재 x 좌표, 현재 길이 )

풀이코드

#include <iostream>
#include <algorithm>
using namespace std;
// 1780 종이의 개수

const int MAX = 2187;

int n;
int ans[3];
int board[MAX][MAX];

bool check(int y, int x, int width){
	int firstValue = board[y][x];
	
	for(int dy = 0; dy < width; dy++){
		for(int dx = 0; dx < width; dx++){
			if(board[y + dy][x + dx] != firstValue) return false;
		}
	}
	// 모든 값이 - 1이면 0번째 인덱스에. 0이면 1번째 인덱스에. 1이면 2번째 인덱스에 +1
	ans[firstValue + 1] += 1;
	return true;
}

// solve(행, 열, 현재 정사각형의 한변의 길이)
void solve(int y, int x, int width){
	// 기저사례 : 모두 같은 수이면 끝
	if(check(y, x, width)) return;
	
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			solve(y + (width / 3) * i , x + (width / 3) * j , width / 3);
		}
	}
}

int main(){
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%d", &board[i][j]);
		}
	}
	solve(0,0,n);
	for(int an : ans) printf("%d ", an);
	cout << endl;
}

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점