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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1780번 문제인 종이의 개수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1780

1780번: 종이의 개수

이 문제는 분할정복(divide and conquer)으로 풀기 좋은 문제이다. 이 문제에서 다음과 같이 분할정복 알고리즘을 적용하자.

 

1) 만약 현재 조각이 한 값으로만 저장되어있다면 그 값의 종이가 하나 있는 것이다.

2) 그렇지 않다면, 종이를 가로 3등분, 세로 3등분 총 9조각 내어 각 조각에 대해 1부터 다시 진행한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int paper[2187][2187];
int m1 = 0, zero = 0, p1 = 0; // 각 종이의 개수를 세는 -1, 0, 1 변수

void solve(int N,int x, int y) {
    int num = paper[x][y];
    bool chk = true;
    for (int i = x;i < x + N;i++) { // 하나의 수로 이루어진 조각인지 확인
        for (int j = y;j < y + N;j++) {
            if (paper[i][j] != num) {
                chk = false;
            }
            if (!chk) break;
        }
        if (!chk) break;
    }
    if (chk) { // 하나의 수로 이루어진 조각이면 그 수에 대응되는 변수를 +1
        if (num == 1) p1++;
        else if (num == 0) zero++;
        else m1++;
    }
    else { // 아니라면 조각을 다시 9조각내어 이를 반복
        N /= 3;
        solve(N, x, y);
        solve(N, x + N, y);
        solve(N, x + 2 * N, y);
        solve(N, x, y + N);
        solve(N, x + N, y + N);
        solve(N, x + 2 * N, y + N);
        solve(N, x, y + 2 * N);
        solve(N, x + N, y + 2 * N);
        solve(N, x + 2 * N, y + 2 * N);
    }
}

int main()
{
    std::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++) {
            int temp;
            cin >> temp;
            paper[i][j] = temp;
        }
    }

    solve(N, 0, 0);

    cout << m1 << '\n' << zero << '\n' << p1;

    return 0;
}