[백준] 2630 색종이 만들기

2630번: 색종이 만들기

 

www.acmicpc.net

풀이

재귀적으로 처리하면 어렵지 않게 해결할 수 있다. 색종이는 1/4의 크기로 계속해서 나뉘어지기 때문에 길이를 1/2로 줄여가면서 색종이를 잘라주면 된다.

코드

#include <iostream>
using namespace std;

int n, w, b;
int paper[128][128];

void countPaper(int sx, int sy, int h) {
    int c = paper[sy][sx];

    bool find = true;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < h; j++)
            if (c != paper[sy + i][sx + j]) {
                find = false;
                break;
            }
    if (find) {
        if (c == 0) w++;
        else b++;
        return;
    }

    countPaper(sx, sy, h / 2);
    countPaper(sx + h / 2, sy, h / 2);
    countPaper(sx, sy + h / 2, h / 2);
    countPaper(sx + h / 2, sy + h / 2, h / 2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> paper[i][j];
    countPaper(0, 0, n);
    cout << w << '\n' << b << '\n';
    return 0;
}