이것저것 개발 블로그

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_2630_색종이만들기 {
    static int[][] paper;
    static int n, blue, white;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        paper = new int[n][n];

        StringTokenizer st;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        devide(0, 0, n);
        System.out.println(white);
        System.out.println(blue);
    }//main
    private static void devide(int x, int y, int size){
        int check = paper[x][y];
        boolean flag = true;
        for(int i=x; i<x+size; i++){
            if(!flag)
                break;
            for(int j=y; j<y+size; j++){
                if(check != paper[i][j]) {
                    flag = false;
                    break;
                }
            }
        }

        if(!flag){
            devide(x, y, size/2);
            devide(x, y+size/2, size/2);
            devide(x+size/2 , y, size/2);
            devide(x+size/2, y+size/2, size/2);
        }
        else{
            if(check == 1)
                blue++;
            else
                white++;
        }

    }//devide
}

솔직히 분할정복임을 알아도 많이 풀어본 적이 없어서 자신이 없었는데,

그래도 규칙성을 찾고 바로 풀 수 있었다!

devide 함수는 parameter로 시작하는 행의 좌표, 시작하는 열의 좌표를 받고, 분할하는 사이즈를 입력받는다.

이렇게 한다면 for문을 도는데 범위를 찾을 수 있다.

분할이 된다는 의미는 색종이의 색이 한 부분이라도 다르다는 의미이므로, 기준 색을 잡는다(check)

분할이 된다면 flag를 false로 하여 for문을 탈출할 수 있도록 한다!

또한 분할이 된다면 4부분으로 분할이 되므로 

devide(x, y, size/2);
devide(x, y+size/2, size/2);
devide(x+size/2 , y, size/2);
devide(x+size/2, y+size/2, size/2);

이렇게 범위를 나눠주면 된다.

그리고 재귀를 이용한다면 알아서 분할해줌!

또한, 우리는 파란색 종이와 하얀색 종이의 개수를 찾아야 하므로,

flag가 true 일 때(분할이 되지 않았을 때) check 변수를 확인해서 개수를 더해주면 끝!

비슷한 문제 다음에 연습해봐야징