[백준] 1780번 종이의 개수

문제

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

풀이과정

분할정복의 기초 문제이다. 문제의 규칙을 보면

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

라고 하고있다. 규칙을 통해 문제 해결법을 생각해보면 종이는 항상 같은 숫자들로만 이루어져있어야 한다. 아니면 9개의 종이로 잘라야 된다.

문제는 (0,0)부터 가로로 n개, 세로로 n개의 종이 개수를 파악해야한다.

하지만 이를 작은 문제로 나눠보면 (x,y)부터 가로로 n개, 세로로 n개의 종이개수를 파악하는 것으로 생각할 수 있다.

말로 설명을 잘 못하겠다. 소스코드를 보는 편이 더 이해가 빠를 것 같다.

소스코드

#include <iostream>

using namespace std;

#define MAX_N 2188

int N;
int paper[MAX_N][MAX_N];
int cnt[3]; // cnt[0] : -1로만 채워진 종이의 개수, cnt[1] : 0으로만 채워진 종이의 개수, cnt[2] : 1로만 채워진 종이의 개수

bool same(int x, int y, int n)
{
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++)
        {
            if (paper[x][y] != paper[i][j])
                return false;
        }
    }

    return true;
}

void solve(int x, int y, int n)
{
    // 같은 숫자로 이루어진 종이면
    if (same(x, y, n))
    {
        cnt[paper[x][y] + 1] += 1;
        return;
    }

    int m = n / 3;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            solve(x+i*m, y+j*m, m);
        }
    }

}


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

    cin >> N;

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

    solve(0, 0, N);

    for (int i = 0; i < 3; i++) cout << cnt[i] << "\n";

    return 0;
}