[BaekJoon/백준] 1780번 분할정복

2630번과 비슷하나, 4개로 쪼개는 것이 아니라 9개로 쪼개는 방식이다.

 

#include <stdio.h>
int arr[2188][2188]; // 3의 7승은 2187
int N;
int result[3]; // [0] = -1 갯수, [1] = 1 갯수, [2] = 2 갯수

// 시작점과 사각형 크기
void divide_conquer(int x, int y, int n) {
    
    int temp = arr[x][y];
    for(int i = x; i < x + n; i++) {
        for(int j = y; j < y + n; j++) {
            
            /*
             포지션
             1 2 3
             4 5 6
             7 8 9
             */
            if(temp != arr[i][j]) {
//                divide_conquer(x, y, n/3); // 1
//                divide_conquer(x, y + n/3, n/3); // 2
//                divide_conquer(x, y + n/3 * 2, n/3); // 3
//
//                divide_conquer(x + n/3, y, n/3); // 4
//                divide_conquer(x + n/3, y + n/3, n/3); // 5
//                divide_conquer(x + n/3, y + n/3 * 2, n/3); // 6
//
//                divide_conquer(x + n/3 * 2, y, n/3); // 7
//                divide_conquer(x + n/3 * 2, y + n/3, n/3); // 8
//                divide_conquer(x + n/3 * 2, y + n/3 * 2, n/3); // 9
                
//                위 9줄의 규칙성을 이용해 아래와 같이 간결하게 구성할 수 있다.
                for(int k = 0; k < 3; k++) {
                    for(int m = 0; m < 3; m++) {
                        divide_conquer(x + (n / 3 * k), y + (n / 3 * m), n/3);
                    }
                }

                
                return; // 더이상 진행할 이유 없음.
            }
        }
    }
            
    result[temp + 1]++; // temp + 1은 -1 0 1 값을 인덱스에 맞춰넣기 위함.
}

int main() {
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    divide_conquer(0, 0, N);
    
    printf("%d\n%d\n%d", result[0], result[1], result[2]);
}