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

문제

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

백준 1780

 

문제 내용

아래 문제와 매우 유사한 문제이다.

[BOJ/백준 2630][C++] 색종이 만들기

1780 종이의 개수 문제 역시 색종이의 개수를 구하는 문제이다.

차이는 2630번은 매번 n/2가 되지만 이 문제는 n/3을 해야 한다는 점, 종이의 종류가 다르다는 점이다.

 

문제 풀이

역시나 재귀를 통해 문제를 풀면 된다.

먼저 종이가 다 같은 수로 채워져 있는지를 체크하고, 그렇지 않으면 9등분하여 분할하여 각각에 대해 같은 과정을 거친다.

만약 다 같은 수로 채워져있으면 종이의 개수를 늘려주면 된다.

 

코드

#include <iostream>
using namespace std;

/**
 * 1. 종이가 다 같은 수로 채워져 있는지 체크
 * 2-1. 그렇지 않으면 분할
 * 2-2. 다 같은 수이면 종이 개수 증가
 */

int arr[2288][2288]; // 3^7=2287
int n;
int cnt[3] = {0, 0, 0}; //-1, 0, 1 종이 개수

bool check(int stR, int stC, int len) {
    int num = arr[stR][stC];

    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (num != arr[stR + i][stC + j]) {
                return false;
            }
        }
    }
    return true;
}

void checkAndDivide(int stR, int stC, int len) {
    if (len == 1 || check(stR, stC, len)) { // 2-2. 다 같은 수일 때
        cnt[arr[stR][stC] + 1]++;
        return;
    }
	
    // 2-1. 다 같지 않으면 9등분으로 분할
    len = len / 3;
    checkAndDivide(stR, stC, len);
    checkAndDivide(stR, stC + len, len);
    checkAndDivide(stR, stC + 2 * len, len);

    checkAndDivide(stR + len, stC, len);
    checkAndDivide(stR + len, stC + len, len);
    checkAndDivide(stR + len, stC + 2 * len, len);

    checkAndDivide(stR + 2 * len, stC, len);
    checkAndDivide(stR + 2 * len, stC + len, len);
    checkAndDivide(stR + 2 * len, stC + 2 * len, len);
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    checkAndDivide(0, 0, n);
    cout << cnt[0] << "\n" << cnt[1] << "\n" << cnt[2];
}