문제 출처: https://www.acmicpc.net/problem/2630

문제 설명

Divide and Conquer 문제이다.

아래의 그림을 보면 이해 하기 쉽다.

1 과 0의 갯수를 찾는 문제인데,

가로와 세로가 2의 배수인 색종이들은 1개의 색종이로 친다.

1 1
1 1 이면 4개의 1이 1개의 1로 바뀌고

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 이면 8개의 1이 1개의 1로 바뀌는 개념이다.

예제 입력

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

예제 출력

9 //0의 개수
7 //1의 개수

문제 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        int[][] board = new int[size][size];

        for (int r = 0; r < board.length; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 0; c < board[0].length; c++)
                board[r][c] = Integer.parseInt(st.nextToken());
        }
        int divide = 1;
        int conquerSize = 0;
        for (int i = 1; i < 8; i++) {
            if (Math.pow(2, i) == size) {
                conquerSize = i;
                break;
            }
        }
        int[] conquerOne = new int[conquerSize + 1];
        int[] conquerZero = new int[conquerSize + 1];
        int conquerIndex = 0;
        while (divide <= size) {
            for (int r = 0; r < size; r += divide) {
                for (int c = 0; c < size; c += divide) {
                    if (count(board, r, c, divide) == 1) {
                        conquerOne[conquerIndex]++;
                    } else if (count(board, r, c, divide) == 0) {
                        conquerZero[conquerIndex]++;
                    }
                }
            }
            divide *= 2;
            conquerIndex++;
        }

        System.out.println(calcTotal(conquerOne));
        System.out.println(calcTotal(conquerZero));
        br.close();
    }

    public static int count(int[][] board, int startPointR, int startPointC, int divide) {
        // -1, 0, 1
        int one = 0;
        int zero = 0;
        for (int r = startPointR; r < startPointR + divide; r++) {
            for (int c = startPointC; c < startPointC + divide; c++) {
                if (board[r][c] == 1)
                    one++;
                else
                    zero++;
            }
        }
        if (one != 0 && zero == 0)
            return 0;
        else if (one == 0 && zero != 0)
            return 1;
        else
            return -1;
    }

    public static int calcTotal(int[] conquer) {
        for(int i = 1; i < conquer.length; i++)
            conquer[i - 1] = conquer[i - 1] - conquer[i] * 4;
        return IntStream.of(conquer).sum();
    }
}

내 문제 풀이 과정은 다음과 같다.

1. 입력을 받아서 2차원 배열을 받는다.

2. 2차원 배열을 사이즈를 확인한 후 개수별로 총 몇개의 1과 0이 있는지 담는다.

예제 입력의 경우

8 사이즈 2차원 배열이므로

0의 개수 [사이즈1 일때, 사이즈 2일때, 사이즈 4일때, 사이즈 8일때] = [30, 7, 0, 0]

1의 개수 [사이즈1 일때, 사이즈 2일때, 사이즈 4일때, 사이즈 8일때] = [34, 8, 1, 0]

4를 곱해서 배열 바로 전 위치의 개수를 뺀다.

30 - 4 x 7 = 2
34 - 4 x 8 = 2
8 - 1 x 4 = 4

0의 개수 = 2 + 7 = 9

1의 개수 = 2 + 4 + 1 = 7

다른 풀이

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

public class Main {
    static int N;
    static int[][] arr;
    static int white, blue = 0;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        square(0, 0, N);
        StringBuilder sb = new StringBuilder();
        sb.append(white + "\n");
        sb.append(blue);
        System.out.println(sb.toString());
    }

    static void square(int r, int c, int n) {
        if (allPainted(r, c, n)) {
            if (arr[r][c] == 0) {
                white++;
            } else {
                blue++;
            }
        } else {
            square(r, c, n/2);
            square(r, c + n/2, n/2);
            square(r + n/2, c, n/2);
            square(r + n/2, c + n/2, n/2);
        }
    }

    static boolean allPainted(int r, int c, int n) {
        int init = arr[r][c];
        for (int i = r ; i < r + n ; i++) {
            for (int j = c ; j < c + n ; j++) {
                if (init != arr[i][j]) return false;
            }
        }
        return true;
    }
}

재귀로 간단하게 했네요.. 이렇게 보니 참 간단한 문제 였던거 같습니다.. 난 어려웠는뎅