1992 쿼드트리

dnc 문제다. dp함수의 인자로는 왼쪽위 좌표 x,y와 정사각형의 크기 s를 넘겨주었으며

x,y부터 s*s사이즈의 배열을 다 돌아보면서 sun에 누적한 후 sum==s*s면 1, 0이면 0, 그것도 아니라면

"("를 출력한 뒤 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래를 조회하고 ")"를 출력하도록 하면 된다.

정사각형 한 변의 크기가 최대 64이므로 int로 받으면 안된다. char로 받거나 %1d로 받으면 편하다.

<코드>

#include <stdio.h>
 
int n, a[64][64];
 
void dp(int x, int y, int s) {
    int sum = 0;
    for (int i = 0; i < s; i++) for (int j = 0; j < s; j++) sum += a[x + i][y + j];
    if (sum == s*s) printf("1");
    else if (!sum) printf("0");
    else {
        printf("(");
        s /= 2;
        dp(x, y, s);
        dp(x, y + s, s);
        dp(x + s, y, s);
        dp(x + s, y + s, s);
        printf(")");
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%1d", &a[i][j]);
    dp(0, 0, n);
    return 0;
}