백준[자바]_분할정복_1780_종이의 개수

오늘은 저번시간에 이어서 분할정복 문제를 풀었다. 분할을 2개로 하는 것이 아닌 3개로 하는 것이기 때문에 조금 까다로울 수 있지만, 이전에 분할정복을 사용한 별찍기 문제를 한 번 풀어보았더니 이 문제는 비교적 쉽게 접근하여 풀 수 있었다.

이 문제를 풀이해보셨다면 아래의 문제도 풀어보시면 좋을 것 같다. basecase만 바꿔주면 된다.

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

2447번: 별 찍기 - 10

 

[ 문제 풀이 ]

• 종이에 적힌 숫자가 모두 동일할 경우 하나의 종이로 센다. 
• 종이는 9개의 칸 즉, 1x1, 3x3, 9x9, ... , 3^k * 3^k의 단위로 보아야 한다. 
• 단순하게 n의 크기를 계속 3으로 분할해서 각 부분문제를 탐색하는데, 모든 값이 초깃값과 동일하다면 카운트를 해주는 식으로 문제를 풀이하면 된다. 

 

package DivideAndConquor;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _1780_종이의수 {
    static int[][] map;
    static int zero, plus, minus;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer  st;
        StringBuilder sb = new StringBuilder();
        
        //색종이의 크기 n*n, n->3^k
        int n = Integer.parseInt(br.readLine());
        
        //맵초기화
        map = new int[n][n];
        for(int i=0;i <n;i++) {
            st = new StringTokenizer(br.readLine());
            for(int k=0; k<n;k++) {
                map[i][k] = Integer.parseInt(st.nextToken());
            }
        }
        
        colorPaper(0, 0, n);
        
        sb.append(minus).append('\n');
        sb.append(zero).append('\n');
        sb.append(plus).append('\n');
        
        System.out.println(sb);
    }
    private static void colorPaper(int x, int y, int size) {
        // TODO Auto-generated method stub
        
        if(isSame(x, y, size)) {
            switch (map[x][y]) {
                case -1: minus++; break;
                case  0: zero++; break;
                case  1: plus++; break;
            }
            return;
        }
        
        int step = size/3;
        
        for(int i=x; i<x+size; i+=step) {
            for(int j=y; j<y+size; j+=step) {
                colorPaper(i, j, step);
            }
        }
        
        
        
    }
    private static boolean isSame(int x, int y, int size) {
        // TODO Auto-generated method stub
        int ans = map[x][y];
        
        for(int i=x; i<x+size; i++) {
            for(int j=y; j<y+size; j++) {
                if(map[i][j] != ans) return false;
            }
        }
        
        return true;
    }
}