[백준 1780] 종이의 개수

문제    www.acmicpc.net/problem/1780

풀이

( 1 ) 문제 쪼개기

기준점(x,y)과 크기(size)를 잡고

주어진  N*N 배열을 9등분한다.

nS = size/3

- ( x , y ,        nS ) ( x+nS , y       , nS )   ( x+2nS , y         , nS ) 

  ( x , y+ nS ,  nS ) ( x+nS , y+ nS , nS )  ( x+2nS , y + nS   , nS )

  ( x , y+2nS , nS ) ( x+nS , y+2nS , nS )  ( x+2nS , y + 2nS , nS )

0	0	0	1	1	1	-1	-1	-1
0	0	0	1	1	1	-1	-1	-1
0	0	0	1	1	1	-1	-1	-1
1	1	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0
0	1	-1	0	1	-1	0	1	-1
0	-1	1	0	1	-1	0	1	-1
0	1	-1	1	0	-1	0	1	-1

(2) 확인하기

각각의 구역에 대해서 확인하고, 

해당 구역 내의 모든 값이 동일할 경우 그대로 출력한다.

해당 구역 내의 값이 다를 경우 (1)을 반복한다.

0			1			-1
1			0			0
0	1	-1	0	1	-1	0	1	-1
0	-1	1	0	1	-1	0	1	-1
0	1	-1	1	0	-1	0	1	-1

코드

/*
 *  Coded by Handal ( 2019.02 )
 */
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader brr = new BufferedReader(new InputStreamReader(System.in));
    static int[][] paper;
    static int[] cutedPapers = new int[3];
    static StringTokenizer stt;
 
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(brr.readLine());
 
        paper = new int[N][N];
        for (int i = 0; i < N; i++) {
            stt = new StringTokenizer(brr.readLine());
            for (int j = 0; j < N; j++)
                paper[i][j] = Integer.parseInt(stt.nextToken());
        }
 
        cut(0, 0, N);
        
        for(int x : cutedPapers)
            System.out.println(x);
    }
 
    static void cut(int x, int y, int size) {
        boolean b = true;
        int std = paper[x][y];
 
        for (int i = x; i < x + size && b; i++)
            for (int j = y; j < y + size && b; j++)
                if (paper[i][j] != std) b = false;
 
        if (b) 
            cutedPapers[std+1]++;
        else {
            int nS = size/3;
            
            for(int i=x;i<x+size;i+=nS)
                for(int j=y; j<y+size; j+=nS) 
                    cut(i, j, nS);
        }
    }
}
 

생각해보기
같은 분할정복 문제라서 그런지 백준1992-쿼드분할 문제와 거의 다른게 없었다.
코드도 1992번 코드에서 4분할을 9분할로 변경하는 부분만 수정했다.