BOJ - 색종이 만들기

https://www.acmicpc.net/submit/2630/33057661

로그인

 

• 입력 값을 이상하게 받아 시간을 허비했던 문제 ㅡ,.ㅡ;
• 꼭 입력이 배열에 정상적으로 들어갔는지 확인하자.
• 해당 문제는 시간 지점에서 Size 별로 더하면서 4분할 확인 과정을 거치면 풀수있다!

 

 

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(whiteCount);
        System.out.println(blueCount);
    }

    private static int blueCount = 0;
    private static int whiteCount = 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) blueCount++;
            if (value == 0) whiteCount++;
            return;
        }

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

        int nextSize = size / 2;
        dp(map, x, y, nextSize);
        dp(map, x + nextSize, y, nextSize);
        dp(map, x, y + nextSize, nextSize);
        dp(map, x + nextSize, y + nextSize, 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) blueCount++;
        if (value == 0) whiteCount++;

        return true;
    }
}