[Java]백준 1780번 :: 종이의 개수

백준 온라인 저지 1780번 '종이의 개수'

Java 알고리즘 문제풀이

풀이

이 문제는 분할정복(Divide and Conquer)로 풀면된다.

분할정복은 정말 쉬운 개념이다.

(유사한 분할정복 문제 풀기 -> 백준 1992번 쿼드트리 https://developer-mac.tistory.com/37)

단순하게 복잡한 문제를 해결할 수 있는 작은단위로 나누어서 처리한 후 이것을 합치면 된다.

이 문제에서 3등분을 한다고 생각하면 된다.

먼저 입력을 받고 divide 함수에서 재귀적으로 동작한 후 if 문을 두어 모든 원소가 0이거나 1일때 빠져나오게 하면 된다.

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

public class beak_1780 {
    private static int n;
    private static int map[][];
    private static int[] count = new int[3];

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());

        map = new int[n][n];

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

        divide(0, 0, n);
        
        System.out.println(count[0]);
        System.out.println(count[1]);
        System.out.println(count[2]);
    }

    private static boolean check(int row, int col, int n) {
        int std = map[row][col];
        for (int i = row; i < row + n; i++) {
            for (int j = col; j < col + n; j++) {
                if (std != map[i][j])
                    return false;
            }
        }
        return true;
    }

    private static void divide(int row, int col, int n) {
        if (check(row, col, n)) {
            count[map[row][col]+1]++;
        } else {
            int s = n / 3;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    divide(row + s * i, col + s * j, s);
                }
            }
        }
    }
}
​