[백준] 2630번 : 색종이 만들기

색종이 만들기

---

해결 방법

이 문제는 자체 문제에 소개하는 부분에 어떻게 해결해야 하는지 잘 나와있다.
이 때문에 난이도에 비해 정답률이 높은듯 함...

대표적인 분할정복 문제로 문제에서 제공하고 있는 그림을 보며 이해하면 쉽게 이해 가능했다.

이 문제에서는 분할 정복 문제가 나오면 구현할 수 있는지 정도만 시험하는 것 같다.

---

코드

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

public class Main {
    //0
    static int white=0;
    //1
    static int blue=0;
    static int[][] paper;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 2, 4, 8, 16, 32, 64, 128 중 하나
        int n = Integer.parseInt(br.readLine());

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

        counter(0,0,n);

        System.out.println(white);
        System.out.println(blue);
    }
    public static void counter(int col,int row,int n){
        int count=0;
        for(int i=col;i<col+n;i++){
            for(int j=row;j<row+n;j++){
                if(paper[i][j] == 1){
                    count++;
                }
            }
        }
        if(count==0){
            white++;
        }
        else if(count==n*n){
            blue++;
        }
        else{ //크기를 반으로 줄임
            // 1 2
            // 3 4
            counter(col,row,n/2);
            counter(col+n/2,row,n/2);
            counter(col,row+n/2,n/2);
            counter(col+n/2,row+n/2,n/2);
        }
    }
}