[백준 1780] 종이의 개수

항상 정사각형으로 나눠지고

크기가 1만 아니면 무조건 9개 3x3형태로 나누므로

 

00 03 06

30 33 36

60 63 66

 

이렇게 각 종이의 시작점으로 구별하고

위 점들에 대해 또 다시 재귀적으로 solve를 해주면 된다

 

한개의 종이가 될 수 있는지는

브루트포스로 직접 다 확인하는 수 밖에 없는듯

어차피 N<=3^7이라 1초 안에는 돌아가는거 같음

 

---

import java.io.*;
import java.util.*;

public class Main {

    static int[][] map = new int[2188][2188];
    static int[] ans = new int[3];

    static void solve(int starty,int startx, int size){
        int cur = map[starty][startx];
        boolean flag = true;

        for(int y=starty;y<starty+size;y++){
            for(int x=startx;x<startx+size;x++){
                if(map[y][x]!=cur){
                    flag = false;
                    break;
                }
            }
            if(!flag) break;
        }

        if(flag) ans[cur+1]++;
        else{
            int newsize = size/3;
            for(int i=0;i<3;i++){
                for(int k=0;k<3;k++){
                    solve(starty+i*newsize, startx+k*newsize, newsize);
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for(int i=1;i<=N;i++){
            String[] s = br.readLine().split(" ");
            for(int k=1;k<=N;k++){
                map[i][k] = Integer.parseInt(s[k-1]);
            }
        }

        solve(1,1,N);

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<3;i++) sb.append(ans[i]).append("\n");
        System.out.println(sb);
    }
}