1780번: 종이의 개수

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


$O(n^2\lg n)$

문제 그대로 구현

#include<cstdio>
int n, a[2187][2187], r[3];
void f(int x, int y, int l) {
    int ck = 0;
    for (int i = x; i < x + l; i++)
        for (int j = y; j < y + l; j++) ck |= a[x][y] != a[i][j];
    if (ck) {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                f(x + l / 3 * i, y + l / 3 * j, l / 3);
    }
    else r[a[x][y] + 1]++;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", a[i] + j);
    f(0, 0, n);
    printf("%d\n%d\n%d", r[0], r[1], r[2]);
    return 0;
}

$O(n^2)$

주어진 구역을 분할해서 함수를 호출하는데
해당 구역에 다른게 있다면 2
전부 같다면 같은 값 -1,0,1 중 하나가 리턴된다고 하자.

구역이 1*1이면 해당 배열값을 리턴한다.
아니면 9개로 분할해서 함수를 호출하고 함숫값 중 2가 있거나 다른 값이 존재하면 2를 리턴하고 동일하면 그 값을 리턴한다.

#include<cstdio>
int n, a[2187][2187], r[3];
int f(int x, int y, int l) {
    int ck = 0, c = a[x][y];
    if (l == 1) {
        r[c + 1]++;
        return c;
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int t = f(x + l / 3 * i, y + l / 3 * j, l / 3);
            if (t == 2 || c^t) ck = 1;
        }
    }
    if (!ck) r[c + 1] -= 8;
    return ck ? 2 : c;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", a[i] + j);
    f(0, 0, n);
    printf("%d\n%d\n%d", r[0], r[1], r[2]);
    return 0;
}