[백준 1780] 종이의 개수 / 자바 / 분할정복(기본)

#문제         

레벨: S2
알고리즘: 분할정복(기본)
풀이시간: 20분
힌트 참조 유무: 무

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

---

#문제 풀이        

이 문제는 피보나치 문제(easy)와 마찬가지로 분할정복의 기초 문제이다. (개인적인 생각으로는 그렇다.)

분할정복 문제를 풀게 된다면 반드시 이 문제는 풀어보고 갔으면 좋겠다.

분할정복 말은 거창하지만  가장 작은 문제로 쪼갤 수 있을 때까지 쪼갠 후 작은 문제들을 풀이하는 것이다. 

이 문제에서는 풀어주세요 ~ 라고 말하는 것처럼 문제를 쪼개는게 직접적으로 나와있다. 

큰 정사각형을 모든 수가 같을 때까지 9등분으로 나누면 되는 것이다. 쉽지 않은가. 나머지는 코드 참고 바란다.

 

---

 

#풀이 코드      

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

class Main {
    
    static int ansM1 = 0;
    static int ans0 = 0;
    static int ans1 = 0;
    static int[][] map;
    
    public static void main(String[] args) throws IOException {
        //입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        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 j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
         
        dfs(N, 0, 0);
        bw.write(ansM1 +"\n");
        bw.write(ans0 +"\n");
        bw.write(ans1 +"\n");
        bw.flush();
        bw.close();
        br.close();
       
    }
    
    //쪼갤 수 있을 때까지 쪼갠다
    public static void dfs(int n, int startX, int startY) {
        if(check(n, startX, startY)) {
            plusAnswer(map[startX][startY]);
            return;
        }
        for(int i = startX; i < startX+n; i+=n/3) {
            for(int j = startY; j < startY+n; j+=n/3) {
                dfs(n/3, i, j);
            }
        }
    } 
    
    //사각형이 다 같은 요소로 이뤄져있는지 확인
    public static boolean check(int n, int startX, int startY) {
         int startNumber = map[startX][startY];
        
        for(int i = startX; i < startX+n; i++){
            for(int j = startY; j < startY+n; j++) {
                if(map[i][j] != startNumber)
                    return false;
            }
        }
        return true;
    }
    
    //수에 따라 변수 ++
    public static void plusAnswer(int n) {
        if(n == -1) 
            ansM1++;
        else if(n == 0)
            ans0++;
        else if(n == 1)
            ans1++;
    }
}