BOJ 2630 - 색종이 만들기

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

분할정복법(Divide and Conquer) 을 사용해 푸는 문제

(참조 : kimch3617.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5%EB%B2%95-Divide-and-Conquer)

 

 

- c++

#include <iostream>
#define MAX 128
 
using namespace std;
 
int adj[MAX][MAX];
int answer[2] = {
    0,
};
int N;
 
void divide_and_conquer(int x, int y, int size) {
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            if (adj[x][y] != adj[i][j]) {
                int s = size / 2;
                divide_and_conquer(x, y, s);
                divide_and_conquer(x + s, y, s);
                divide_and_conquer(x, y + s, s);
                divide_and_conquer(x + s, y + s, s);
                return;
            }
        }
    }
    answer[adj[x][y]]++;
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> adj[i][j];
        }
    }
 
    divide_and_conquer(0, 0, N);
 
    cout << answer[0] << '\n';
    cout << answer[1] << '\n';
 
    return 0;
}

 

 

 

 

코드 원 출처 : blog.naver.com/PostView.nhn?blogId=jqkt15&logNo=221943964277

[Boj 2630] 백준 - 색종이 만들기 (분할 정복, 재귀)