[C++] BAEKJOON 1780 종이의 개수

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

1780번: 종이의 개수

분할정복 을 사용하여 문제를 해결하였습니다.

문제를 해결하는 핵심 함수 check 와 배열의 원소들이 같은지 확인하는 same 함수를 이용하여 문제를 해결하였습니다. 배열의 모든 값이 같은지 확인을 하고 같다면 count 를 올려주고 같지 않다면 9개로 나누어 다시 check 함수로 확인을 하였습니다.

#include <iostream>

using namespace std;

int board[2187][2187];

// index 0 : -1 개수, index 1 : 0 개수, index 2 : 1개수
int countNum[3];
int N;

int same(int y,int x,int N){
    int temp = board[y][x];
    for (int i=y;i<y+N;i++){
        for (int j=x;j<x+N;j++){
            if (temp != board[i][j])
                return 0;
        }
    }
    return 1;
}

void check(int y,int x,int N){
    
    if (same(y,x,N)){
        countNum[board[y][x]+1] ++;
        return;
    }
    
    int M = N/3;
    for (int i=0;i<3;i++){
        for (int j=0;j<3;j++){
            check(y+M*i,x+M*j,M);
        }
    }
    
}

int main(int argc, const char * argv[]) {
    
    cin >> N;
    
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cin >> board[i][j];
        }
    }
    
    check(0,0,N);
    
    for (int i=0;i<3;i++){
        cout << countNum[i] << "\n";
    }
    return 0;
}