[분할 정복] / [백준(baekjoon) 1780] 종이의 개수

문제

백준 1780

N x N 크기의 행렬은 -1, 0, 1의 값을 가진다.
다음과 같은 규칙으로 종이를 자른 후, -1, 0, 1로만 채워진 종이의 개수를 차례대로 출력하시오.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

해결

알고리즘

전형적인 분할 방식 문제이다.

방법

• 큰 종이를 9개의 작은 종이로 나누는 과정을 반복한다.
  
  • 시작점, n을 매개변수로 받아 구하고자 하는 종이의 크기 및 값들에 접근할 수 있다.
  • 3 * 3 for문을 돌린다. 작은 종이의 크기는 n / 3이 될 것이다.
  • 종이의 크기 n == 1까지 반복한다.
• 리턴 값은 종이 내 -1, 0, 1 각각의 개수를 담고있는 int []배열이다.
  
  • n = 1의 경우 해당 값만 1로 표시해 내보낸다.
  • 나머지의 경우 우선 9개의 작은 종이 들의 결과 값들을 모두 더한다.
  • 만약 9개의 종이가 모두 특정 값을 가르킨다면 해당 값의 개수가 9가 될 것이다.
  • 이 경우 하나의 종이가 되므로 9 -> 1로 변경한다.

구현 java

1.import java.util.*;
2.
3.public class Main {
4.    static int[][] map;
5.    public static void main(String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int n = sc.nextInt();
8.        map = new int[n][n];
9.        for (int i = 0; i < n; i++) {
10.            for (int j = 0; j < n; j++) {
11.                int input = sc.nextInt();
12.                if (input == -1) input = 2;
13.                map[i][j] = input;
14.            }
15.        }
16.        int[] result = getCount(new int[]{0, 0}, n);
17.        System.out.println(result[2]);
18.        System.out.println(result[0]);
19.        System.out.println(result[1]);
20.    }
21.
22.    static int[] getCount (int[] s, int n) {
23.        int[] count = new int[3];
24.        if (n == 1) {
25.            count[map[s[0]][s[1]]]++;
26.            return count;
27.        }
28.        int last = 3;
29.        for (int i = s[0]; i < s[0] + n; i += n / 3) {
30.
31.            for (int j = s[1]; j < s[1] + n; j += n / 3) {
32.                int[] result = getCount(new int[]{i, j}, n / 3);
33.                for (int k = 0; k < 3; k++) {
34.                    if (result[k] > 0) last = k;
35.                    count[k] += result[k];
36.                }
37.            }
38.        }
39.        if (count[last] == 9)
40.            count[last] = 1;
41.        return count;
42.    }
43.}

결과

의문

메인 부분의 코드가 너무 더러워서 아래처럼 더욱 간결하게 변경했는데 틀렸다고 뜬다.

1.public static void main(String[] args) {
2.    Scanner sc = new Scanner(System.in);
3.    int n = sc.nextInt();
4.    map = new int[n][n];
5.    for (int i = 0; i < n; i++) {
6.        for (int j = 0; j < n; j++) {
7.            map[i][j] = sc.nextInt() + 1;
8.        }
9.    }
10.    for (int c : getCount(new int[]{0, 0}, n))
11.        System.out.println(c);
12.}

기존 코드가 -1를 가르킬 인덱스를 2로 지정하여
출력 순서를 불가피하게 2(-1) -> 0 -> 1로 했다면,
수정한 코드는 입력 값 + 1을 해주어 인덱스를 순서에 맞게 바로 가르켜
출력 순서가 0(-1) -> 1(0) -> 2(1) 순서로 정확히 되는 것을 확인했다.

근데 틀린다!!!!!!!! 이유를 정말 모르겠다.

수많은 흔적들…