[BOJ/c++] 1780 - 종이의 개수

문제

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

1780번: 종이의 개수

해설

자른 종이안에 1, 0, -1 중 하나만 저장 되어 있는지 확인 하는 과정을 일일이 하면 시간 초과가 날까봐 어렵게 푼 문제이다.. (시간 복잡도 계산해보면 최악의 경우에도 가능)

구간합을 공부했던 것에 착안을 얻어 이차원 배열에서 d[i][j] = (1,1) ~ (i,j) 까지 -1,0,1의 개수를 저장해줬다 구조체를 사용했기 때문에 연산의 편의성을 위해 연산자 오버로딩을 해줬다.

코드

#include <iostream>
#include <vector>
using namespace std;

struct Paper {
    int m; // -1
    int z; // 0
    int p; // 1
    Paper operator+(Paper a) {
        Paper ret;
        ret.m = this->m + a.m;
        ret.z = this->z + a.z;
        ret.p = this->p + a.p;
        return ret;
    }
    Paper operator-(Paper a) {
        Paper ret;
        ret.m = this->m - a.m;
        ret.z = this->z - a.z;
        ret.p = this->p - a.p;
        return ret;
    }
};

Paper d[2188][2188];
int v[2188][2188];
int n;

Paper ans;

void func(int a, int b, int n) {
    Paper t = d[a + (n - 1)][b + (n - 1)] - d[a + (n - 1)][b - 1] - d[a - 1][b + (n - 1)] + d[a - 1][b - 1];
    if (t.m == n * n) {
        ans.m += 1;
        return;
    } else if (t.z == n * n) {
        ans.z += 1;
        return;
    } else if (t.p == n * n) {
        ans.p += 1;
        return;
    } else {
        for (int i = 0; i < 3; i++) 
        for (int j = 0; j < 3; j++)
        func(a + (n / 3) * i, b + (n / 3) * j, n / 3);
    }
    return;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> v[i][j];
            if (v[i][j] == 1) {
                d[i][j].p = d[i][j - 1].p + 1;
                d[i][j].z = d[i][j - 1].z;
                d[i][j].m = d[i][j - 1].m;
            } else if (v[i][j] == 0) {
                d[i][j].z = d[i][j - 1].z + 1;
                d[i][j].p = d[i][j - 1].p;
                d[i][j].m = d[i][j - 1].m;
            } else if (v[i][j] == -1) {
                d[i][j].m = d[i][j - 1].m + 1;
                d[i][j].z = d[i][j - 1].z;
                d[i][j].p = d[i][j - 1].p;
            }
        }
    }
    for (int i = 1; i <= n ; i++) {
        for (int j = 1; j <= n; j++) {
            d[j][i] = d[j - 1][i] + d[j][i];
        }
    }
    func(1, 1, n);
    cout << ans.m << '\n' << ans.z << '\n' << ans.p;
    return 0;
}