[BOJ] #2630 색종이 만들기

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

2630번: 색종이 만들기

---

재귀함수 호출을 통해 해결해야 하는 문제이다. 처음엔 주어진 전체 넓이 N을 탐색하다가 조건에 맞지 않으면 재귀적 호출을 통해 4등분된 넓이들을 조건에 맞는 모양이 나올때까지 탐색해야한다.

만들어진 코드 자체는 간단하게 보여도, 매커니즘을 떠올리는것이 좀 어려웠다. 특히 재귀함수에 전달할 인자들을 설정하고 범위를 지정해주는것에 많은 시간을 할애했던 것 같다. 재귀함수 문제도 많이 풀어보면서 감각을 잘 익혀두어야 할 것 같다.

#include <iostream>

#define MAX 130

using namespace std;

int cnt0, cnt1;
int arr[MAX][MAX];

void F(int x, int y, int n) {
    int tmp = 0;
    
    for (int i=x; i<x+n; i++) {
        for (int j=y; j<y+n; j++) {
            if (arr[i][j] == 1) tmp++;
        }
    }

    if (tmp == 0) cnt0++;
    else if (tmp == n*n) cnt1++;
    else {
        F(x, y, n/2);
        F(x + n/2, y, n/2);
        F(x, y + n/2, n/2);
        F(x + n/2, y + n/2, n/2);
    }

    return ;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            int a;
            cin >> a;

            arr[i][j] = a;
        }
    }

    F(0,0,N);

    cout << cnt0 << '\n' << cnt1 << '\n';

    return 0;
}

재귀함수 호출 시 범위값을 잘못 설정하여 시간초과가 났었다. 범위만 수정했더니 바로 맞았다.