1992번: 쿼드트리

https://www.acmicpc.net/problem/1992


$O(n^2)$

#include<cstdio>
int n, s[65][65];
void f(int x, int y, int l) {
    int t = s[x + l][y + l] - s[x][y + l] - s[x + l][y] + s[x][y];
    if (!t || t == l*l) printf("%d", t>0);
    else {
        printf("(");
        for (int i = 0; i < 4; i++) f(x + i / 2 * l / 2, y + i % 2 * l / 2, l / 2);
        printf(")");
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        scanf("%1d", &s[i][j]), s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
    f(0, 0, n);
    return 0;
}