[Algorithm] Baekjoon 1780번 : 종이의 개수

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

1780번: 종이의 개수

int paper[2200][2200];
map<int, int> countMap;
 
void recur(int leftTopY, int leftTopX, int size)
{
    int element = paper[leftTopY][leftTopX];
    bool isDivide = false;
 
    for (int i = leftTopY; i < leftTopY + size; i++)
    {
        for (int j = leftTopX; j < leftTopX + size; j++)
        {
            if (paper[i][j] != element)
            {
                isDivide = true;
                break;
            }
        }
    }
 
    if (!isDivide)
    {
        countMap[element] += 1;
        return;
    }
 
    // 분할.
 
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            recur(leftTopY + i * size / 3, leftTopX + j * size / 3, size / 3);
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> paper[i][j];
        }
    }
 
    recur(0, 0, n);
 
    cout << countMap[-1] << endl << countMap[0] << endl << countMap[1];
    return 0;
}

이제 분할문제도 나름 쉽게 풀수 있게 되었다.

현재 solved.ac에서 class 3의 문제들만 풀고 있는데, 이런 유형의 문제가 벌써 3개가 나온걸 보니 나름 중요한 유형인가보다. 

이 문제도 이전문제들과 똑같이 영역내의 원소가 같은지 체크하고 아니면 분할하는 그런 문제다.