문제
https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
코드
#include <iostream>
using namespace std;
int paper[128][128];
int white = 0;
int blue = 0;
void cutPaper(int y, int x, int size){
bool flag = false;
int check = paper[y][x];
for(int i=y; i < y+size; i++){
for(int j=x; j< x+size; j++){
if(check != paper[i][j]){
flag = true;
break;
}
}
if(flag){
break;
}
}
if(!flag){
if(check == 1){
blue++;
} else if(check == 0){
white++;
}
}else{
int half = size/2;
cutPaper(y, x, half);
cutPaper(y, x+half, half);
cutPaper(y+half, x, half);
cutPaper(y+half, x+half, half);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> paper[i][j];
}
}
cutPaper(0,0,n);
cout << white << '\n' << blue;
return 0;
}정리
분할 정복(Divide & Conquer)이란?
분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 보통 재귀 함수를 통해 자연스럽게 구현된다.
function F(x):
if F(x)의 문제가 간단 then:
return F(x)을 직접 계산한 값
else:
x를 y1, y2로 분할
F(y1)과 F(y2)를 호출
return F(y1), F(y2)로부터 F(x)를 구한 값
분할 정복의 진행방식
분할 → 정복 → 조합
분할 : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
정복 : 가장 작은 단위의 하위 문제를 해결하여 정복한다.
조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
참조
'Beakjoon > divide & conquer' 카테고리의 다른 글
| [백준] 1074번 Z (C++) - divide & conquer (0) | 2022.02.18 |
|---|---|
| [백준] 1992번 쿼드트리 (C++) - divide & conquer (0) | 2022.02.17 |
| [백준] 2447번 별 찍기 - 10 (C++) - divide & conquer (0) | 2022.02.16 |
| [백준] 1780번 종이의 개수 (C++) - divide & conquer (0) | 2022.02.16 |
