[BOJ1780][C++] 종이의 개수

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

1780번: 종이의 개수

문제

예제를 보면 문제가 더 잘 이해된다.

3^n*3^n (n>=0)으로 이루어진 -1, 0, 1의 개수를 각각 구하는 문제이다.

 

해결

🎈Key Point🎈

-1, 0, 1로만 각각 이루어진 3^n*3^n 배열을 찾는 것이 포인트인데, 여기서 생각할 수 있는 점은 n에 대하여 탐색 후(3^n*3^n 배열 탐색) 조건에 맞지 않으면 n/3에 대하여, 또 안맞으면 다시 (n/3)/3... 이런 식으로 n을 계속해서 3으로 나누면서 탐색해나갈 수 있다는 것이다. => 여기서 재귀를 생각했다.

*재귀로 문제를 해결한다*

 

어떠한 값 k에 대하여 3^k*3^k의 배열의 시작점을 행,열 값이 가장 작은 위치로 설정한다. 따라서 가장 첫 시작은 k=n일 때 (0,0)이 된다.

시작점부터 끝점(배열에서 가장 오른쪽 하단)까지 숫자를 탐색하여 모두 같은 수(-1,0 또는 1)로 이루어져있으면 해당 숫자로 이루어진 종이의 개수를 1 증가시킨다.

만약 모든 숫자가 같지 않다면 k를 3으로 나누고(k/3) 9등분된 각 배열들을 탐색한다. 이 때, 각 배열의 시작점을 마찬가지로 가장 왼쪽 위로 설정하면 되고, k/3과 해당 시작점을 가지고 과정을 반복한다.

 

<상세코드 설명>

- 3^n*3^n 배열이 모두 같은 수로 이루어져있으면 해당 숫자 종이의 개수를 증가시키고, 그렇지 않으면 다음단계로 넘어간다.

int num = paper[a][b];	// 시작점의 숫자 저장(-1, 0, 1)
bool tf = true;		// 배열이 모두 같은 수로 이루어져있는지 판단
for (int i = a; i < a + n; i++) {	// 시작점부터 배열의 가장 왼쪽 아래까지 숫자 탐색
    for (int j = b; j < b + n; j++) {
        if (paper[i][j] == num) continue;
        else {		// 배열이 모두 같은 수로 이루어져있지 않음
            tf = false;	
            break;
        }
    }
}
if (tf) {	// 배열이 모두 같은 수로 이루어져있어 tf의 값이 true로 유지됨
    count(a, b);	// 종이 개수 증가하는 메소드
    return;
}

- 3^n*3^n 배열이 모두 같은 숫자로 이루어져있지 않을 경우, n/3에 대해 재탐색

// n/3
// 시작점(9개): (a, b), (a+(n/3),b), (a+2(n/3),b), (a,b+(n/3)), (a+(n/3),b+(n/3)), (a+2(n/3),b+(n/3)), (a,b+2(n/3)), (a+(n/3),b+2(n/3)), (a+2(n/3),b+2(n/3)) 
for (int k = 0; k < 3; k++) {
    for (int l = 0; l < 3; l++) {
        findPaper(n / 3, a + k * (n / 3), b + l * (n / 3));
    }
}

 

[전체 코드]

#include <iostream>

using namespace std;

int paper[3000][3000];
int mone = 0;
int zero = 0;
int one = 0;

void count(int a, int b) {
	if (paper[a][b] == -1) mone++;
	else if (paper[a][b] == 0) zero++;
	else one++;
}

void findPaper(int n, int a, int b) {
	if (n == 1) {
		count(a, b);
		return;
	}

	int num = paper[a][b];	// 시작점의 숫자 저장(-1, 0, 1)
	bool tf = true;		// 배열이 모두 같은 수로 이루어져있는지 판단
	for (int i = a; i < a + n; i++) {	// 시작점부터 배열의 가장 왼쪽 아래까지 숫자 탐색
		for (int j = b; j < b + n; j++) {
			if (paper[i][j] == num) continue;
			else {		// 배열이 모두 같은 수로 이루어져있지 않음
				tf = false;
				break;
			}
		}
	}
	if (tf) {	// 배열이 모두 같은 수로 이루어져있어 tf의 값이 true로 유지됨
		count(a, b);	// 종이 개수 증가하는 메소드
		return;
	}

	// n/3
	// 시작점(9개): (a, b), (a+(n/3),b), (a+2(n/3),b), (a,b+(n/3)), (a+(n/3),b+(n/3)), (a+2(n/3),b+(n/3)), (a,b+2(n/3)), (a+(n/3),b+2(n/3)), (a+2(n/3),b+2(n/3)) 
	for (int k = 0; k < 3; k++) {
		for (int l = 0; l < 3; l++) {
			findPaper(n / 3, a + k * (n / 3), b + l * (n / 3));
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++)
			cin >> paper[i][j];
	
	findPaper(N, 0, 0);

	cout << mone << "\n" << zero << "\n" << one;
}