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

2630번과 아주 비슷한 문제였다.

 

// 땅 나누기가 시작될 때 괄호가 열리고, 끝날 때 닫힘.

#include <stdio.h>
int arr[64][64];
int N;

// 시작점과 사각형 크기
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++) {
            
            if(temp != arr[i][j]) {
                printf("(");
                divide_conquer(x, y, n/2);
                divide_conquer(x, y + n/2, n/2);
                divide_conquer(x + n/2, y, n/2);
                divide_conquer(x + n/2, y + n/2, n/2);
                
                printf(")");
                return; // 더이상 진행할 이유 없음.
            }
        }
    }
            
    
    if(temp == 1)
        printf("1");
    else
        printf("0");
}

char input[65];
int main() {
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        scanf("%s", input);
        
        for(int j = 0; j < N; j++) {
            arr[i][j] = input[j] - '0';
        }
    }
    divide_conquer(0, 0, N);
}