1780번

1780번 - 종이의 개수

이 문제는 분할 정복으로 문제를 풀었다.

일단 같은 방식이 계속해서 이어지기 때문에, 그에 따라 재귀함수를 수행시켰다.

ans 배열은 종이의 갯수를 담도록 크기를 3으로 지정하고, -1의 종이 갯수는 index 0에, 0의 종이 갯수는 index 1에 , 1의 종이 갯수는 index 2에 저장했다. 

재귀함수에서 크기가 1인경우, 즉 n==1 인 경우에는 곧 바로 해당하는 종이의 갯수값을 증가시켰다.

그러지 않을 경우에는 전체 맵을 돌게 만들었고, 전체 맵이 하나의 숫자로만 이루어진 경우는 또 종이의 값을 증가시켰다.

하지만 하나의 숫자가 아닐 경우에는 9개의 종이를 재귀탐색 하도록 설정하였다.

종만북에 있는 문제와 비슷하다. 종만북 풀때 다시 풀어볼 것, 종만북과 나의 풀이 비교확인 해보기.

<정답 코드>

#include<iostream>
 
using namespace std;
 
int map[3001][3001];
int ans[3];
void check(int start_x, int start_y,int n)
{
 
    int tmp = map[start_x][start_y];
    bool perfect = true;
 
    if (n == 1)
    {
        ans[tmp + 1]++;
        return;
    }
    for (int i = start_x; i < start_x+n; i++)
    {
        for (int j = start_y; j < start_y+n; j++)
        {
            if (tmp != map[i][j])
            {
                perfect = false;
                for (int a = 0; a< 3; a++)
                {
                    for (int b = 0; b < 3; b++)
                    {
                        check(start_x + (a*(n / 3)), start_y + (b*(n / 3)), n / 3);
                    }
                }
                break;
            }
        }
 
        if (!perfect)
        {
            break;
        }
    }
 
    if (perfect)
    {
        ans[tmp + 1]++;
    }
    
    return ;
}
int main()
{
    int N;
 
    cin >> N;
    
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> map[i][j];
        }
    }
 
    check(1,1,N);
 
    for (int i = 0; i < 3; i++)
    {
        cout << ans[i] << endl;
    }
}