백준 2630번 - 색종이 만들기

재귀 혹은 분할정복(Divide & Conquer) 문제인데, 은근 시간이 오래 걸렸다. 재귀 아이디어는 금세 나왔는데, 소소한 기본이 이슈가 있어서 자꾸만 문제를 다시 풀게 되었다.

처음에는 2차원 vector을 이용해서 풀었는데, size가 커지면 에러가 발생했다. 알고보니 vector을 함수의 인수(parameter)로 넘겨주면 그때마다 vector가 복사되기 때문에, 시간 초과가 발생할 수 있다. 이를 막기 위해서는 참조사를 이용하거나, int paper[128][128]처럼 int 배열을 이용해야한다.

#include <iostream>

using namespace std;

int n_0 = 0;
int n_1 = 0;
int paper[128][128];

void epoch(int size, int x, int y){

    int n_sum = 0;
    for (int i=x; i<x+size; i++){
        for (int j=y; j<y+size; j++){
            if (paper[i][j] == 1){
                n_sum ++;
            }
        }
    }
    
    if (n_sum == size*size){
        n_1 ++;
    } else if (n_sum == 0){
        n_0 ++;
    } else{
        size /= 2;
        epoch(size, x, y);
        epoch(size, x+size, y);
        epoch(size, x, y+size);
        epoch(size, x+size, y+size);
    }
}

int main()
{
    int size;
    cin >> size;
    
    for (int i=0; i<size; i++){
        for (int j=0; j<size; j++){
            cin >> paper[i][j];
        }
    }
    epoch(size, 0, 0);
    
    cout << n_0 << endl << n_1;

    return 0;
}

Comments: