2630 백준 C++

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

 

위 문제를 풀었다. 분할 정복 문제는 가장 크게 3가지를 위주로 고민하면 된다.

 

1. 재귀를 언제까지 지속하는가?

2. 어떻게 나눠야 할까?

3. 어떻게 나눈 것을 합칠까?

 

이렇게 3가지를 고려하면 되는데 이걸 머리에 넣고 고민해보자....

 

 

문제를 대충 요약해서 보면..

계속해서 n/2로 나눠지고.. 문제를 읽어보면 1x1 grid를 가지고 있으면 그냥 그 색으로 간다고 한다.

 

그렇다면 

n이 1이면 분할을 멈춰야 할 것이고. 

n * n grid에 다른 색이 있다면 n/2로 나누어서 다시 호출해야 할 것이다. 

그리고 총 4가지의 면으로 쪼개니까.

아래처럼 시작 값에 n/2를 각각 맞게 더해주면 될 것이다.

 

#include <iostream>
#include <vector>

using namespace std;

int arr[129][129];
int dap[2] = { 0, }; // 0이면 휜 1이면 파랑

void solve(int n, int x, int y) {

	//1. 종료조건
	if (n == 1) {
		dap[arr[x][y]]++;
		return;
	}


	//2. 나누는 방식
		for (int i = x; i < x + n; i++) {
			for (int k = y; k < y + n; k++) {
			
				if (arr[x][y] != arr[i][k]) {
				
					solve(n/2, x, y);
					solve(n / 2, x + n/2, y);
					solve(n / 2, x, y + n/2);
					solve(n / 2, x + n/2, y + n/2);
					
				
					return;
				}
			
			}
		}

		//3 합치기 -> 없음

		dap[arr[x][y]]++;
}

int main() {

	int n;

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int k = 0; k < n; k++)
			cin >> arr[i][k];

	solve(n, 0, 0);

	cout << dap[0] << '\n' << dap[1];

	return 0;
}