[백준 C++] 2630 : 색종이 만들기

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

예시로 주어진 사진과 함께 생각해보면 2의 배수로 주어지는 N이 나눌때마다 2 / N로 계속 줄어드는 것을 볼 수 있다.

 

즉 첫 시작점만 정해주게 되면 줄어드는 값을 더해 끝점을 구할 수 있고, 시작점과 끝점 안에 있는 내용을 확인하여 색이 모두 일치하는지 보면 된다.

---

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<vector<int>> board;
vector<int> answer;

void solve(int sX, int sY, int size)
{
	if (size == 0)
		return;

	bool bClear = true;
	int color = board[sY].at(sX);

	for (int y = sY; y < sY + size; y++)
	{
		for (int x = sX; x < sX + size; x++)
		{
			if (color != board[y].at(x))
			{
				bClear = false;
				break;
			}
		}
	}

	if (bClear)
	{
		if (color == 0)
			answer[0]++;
		else
			answer[1]++;
	}
	else
	{
		solve(sX, sY, size / 2);
		solve(sX + (size / 2), sY, size / 2);
		solve(sX, sY + (size / 2), size / 2);
		solve(sX + (size / 2), sY + (size / 2), size / 2);
	}
}

int main()
{
	cin >> N;

	board = vector<vector<int>>(N, vector<int>(N, 0));
	answer = vector<int>(2, 0);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int temp;
			cin >> temp;

			board[i].at(j) = temp;
		}
	}
	
	solve(0, 0, N);

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

	return 0;
}

색을 확인하기 위해 bool변수인 bClear를 이용하였고 나머지는 재귀로 구현하였다.