1780번 종이의 개수

문제 링크

종이의 개수

문제 풀이

사각형 안에 저장된 수가 모두 같다면 그대로 사용하고, 다른 경우 이를 9개로 나누는 문제이다. 사각형 안의 수를 보고 다 같다면 멈추고, 아닐 시 범위를 나눠어 9번의 재귀 호출을 하면 된다.

구현

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

int N;
vector<int> ans(3, 0);
vector<vector<int>> board(3000, vector<int>(3000, 0));

void solve(int y, int x, int size) {
    int cnt[3] = { 0, };

    for (int i = 0; i < size; ++i)
        for (int j = 0; j < size; ++j)
            ++cnt[board[y + i][x + j] + 1];

    for (int i = 0; i < 3; ++i) {
        if (cnt[i] == size * size) {
            ++ans[i];
            return;
        }
    }

    int subSize = size / 3;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            solve(y + subSize * i, x + subSize * j, subSize);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> board[i][j];
    solve(0, 0, N);
    for (int i = 0; i < 3; ++i)
        cout << ans[i] << endl;
    return 0;
}