[백준 1780] 종이의 개수

 

분할정복을 사용하는 전형적인 문제이다.

 

종이의 크기를 9로 예를 들면

1. 9*9 를 탐색한다.

2. 종이가 모두 같은 수로 되어있지 않다면 9등분하여 각 종이를 탐색한다.

3. 2번을 반복하여 -1, 0, 1 의 개수를 센다.

 

2번이 계속 반복되므로 재귀함수로 짜주기만 하면 된다.

 

코드를 보고 머리로 그려보는 것이 좋을 것 같다.

 

public class Main {
    
    static int a[][];
    static int cnt[] = new int[3];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        a = new int[n][n];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        recursive(0, 0, n);
        for(int i=0; i<3; i++)
            System.out.println(cnt[i]);
    }
    
    public static void recursive(int r, int c, int len) {
        boolean f = true;
        int def = a[r][c];
        for(int i=r; i<r+len; i++) {
            for(int j=c; j<c+len; j++) {
                if(def != a[i][j]) {
                    f = false;
                    break;
                }
            }
        }
        
        if(!f) {
            int m = len/3;
            for(int i=0; i<3; i++) {
                for(int j=0; j<3; j++) {
                    recursive(r + i*m, c + j*m, m);
                }
            }
        } else cnt[a[r][c]+1]++;
    }
}