[백준] 1780번 종이의 개수 c++

recursion으로 접근한다.

 

BaseCase

1) n=1인 경우에는 각 케이스에 맞게 count를 1증가시키고 종료해준다.

 

RecursionCase

1) 모든 칸이 동일한 숫자로 채워져 있다면 해당 숫자에 맞게 count를 1증가시키고 종료해준다.

2) 그렇지 않다면 9개의 구역에 해당하는 recursion을 실행한다.

#include <iostream>
#include <math.h>

using namespace std;

int a[2200][2200] = {0,};
int count[3] = {0,};

void solve(int x, int y, int n){
    if(n==1){
        if(a[x][y] == -1)
            ::count[0]++;
        if(a[x][y] == 0)
            ::count[1]++;
        if(a[x][y] == 1)
            ::count[2]++;
        return;
    }

    int target = a[x][y];
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++){
            if(target != a[i][j]){
                int d = n / 3;
                for (int c = 0; c < d * 3; c+=d){
                    for (int l = 0; l < d * 3; l += d)
                    {
                        int dx = x + c;
                        int dy = y + l;
                        solve(dx, dy, d);
                    }
                }
                return;
            }
        }
    }

    if(a[x][y] == -1)
        ::count[0]++;
    if(a[x][y] == 0)
        ::count[1]++;
    if(a[x][y] == 1)
        ::count[2]++;

    return;
}

int main()
{
    int n;
    cin >> n;

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

    for (int i = 0; i < 3; i++){
        cout << ::count[i] << "\n";
    }
}