BOJ - 종이의 개수

https://www.acmicpc.net/submit/1780/33059203

로그인

 

• 날먹 문제이다!
• 색종이 만들기가 4분할 문제를 9분할 문제로 변경하면 쉽게 해결 할 수 있다!
• https://developer-h.tistory.com/entry/BOJ-%EC%83%89%EC%A2%85%EC%9D%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0

 

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


public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N + 1][N + 1];

        for (int i = 0; i < N; i++) {
            String[] tokens = br.readLine().split(" ");
            for (int j = 0; j < tokens.length; j++) {
                map[i][j] = Integer.parseInt(tokens[j]);
            }
        }

        dp(map, 0, 0, N);

        System.out.println(minusCount);
        System.out.println(zeroCount);
        System.out.println(plusCount);
    }

    private static int minusCount = 0;
    private static int zeroCount = 0;
    private static int plusCount = 0;

    private static void dp(int[][] map, int x, int y, int size) {
//        System.out.printf("%d %d %d\n", x, y, size);
        if (size == 1) {
            int value = map[y][x];
            if (value == -1) minusCount++;
            if (value == 0) zeroCount++;
            if (value == 1) plusCount++;
            return;
        }

        if (isFill(map, x, y, size)) {
            return;
        }

        int nextSize = size / 3;
        dp(map, x, y, nextSize);
        dp(map, x + nextSize, y, nextSize);
        dp(map, x + nextSize * 2, y, nextSize);

        dp(map, x , y + nextSize, nextSize);
        dp(map, x + nextSize, y + nextSize, nextSize);
        dp(map, x + nextSize * 2, y + nextSize, nextSize);

        dp(map, x, y + nextSize * 2, nextSize);
        dp(map, x + nextSize, y + nextSize * 2, nextSize);
        dp(map, x + nextSize * 2, y + nextSize * 2, nextSize);
    }

    private static boolean isFill(int[][] map, int x, int y, int size) {
        int value = map[y][x];
        for (int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                if (value != map[i][j]) {
                    return false;
                }
            }
        }
        if (value == -1) minusCount++;
        if (value == 0) zeroCount++;
        if (value == 1) plusCount++;

        return true;
    }
}