[분할정복] 색종이 만들기

백준 2630 www.acmicpc.net/problem/2630

 

Cond 1. 입력은 2의 배수이며, 마찬가지로 색종이도 반으로 분할만 가능하다. 

Cond 2. 종이의 분할은 선택한 부분이 전부 파란색이거나, 하얀색일때까지 진행하게 된다.

 

재귀함수로 종이의 분할을 구현한다.

Seq 1. 종이를 위치(row, col)과 크기(size)를 이용하여 읽어낸다.

Seq 2. 종이에 색칠할 수 있는 좌표의 갯수(size*size)의 파란색(1)의 갯수를 더한다.

Seq 3. 모든 좌표가 파란색이면(합이 size*size) 파란색 종이 수를 뜻하는 변수에 1을 더한다.

Seq 4. 모든 좌표가 하얀색이면(합이 0) 하얀색 종이 수를 뜻하는 변수에 1을 더한다. 

Seq 5. 3, 4 둘다 아니라면 다시 종이를 분할하여 4부분을 세아린다. 

 

#include<stdio.h>

int arr[130][130];
int white, blue;

void recur(int row, int col, int size){
    int count = 0;
    for(int i=col; i<size+col; i++)
        for(int j=row; j<size+row; j++)
            if(arr[i][j] == 1) count += 1;
    if(count == size*size) blue += 1;
    else if(count == 0) white += 1;
    else if(size != 1) {
        recur(row, col, size/2);
        recur(row, col+size/2, size/2);
        recur(row+size/2, col, size/2);
        recur(row+size/2, col+size/2, size/2);
    }
}

void split(int n){
    recur(0, 0, n);
    printf("%d\n%d", white, blue);
}

int main(){
    int N;
    scanf("%d", &N);
    for(int i = 0; i<N; i++)
        for(int j = 0; j<N; j++)
            scanf("%d", &arr[i][j]);
    split(N);
}