BOJ 2630 색종이 만들기

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

이런 문제다.

그렇다면, 분할정복 기법을 사용한다. 어차피 1*1 2*2 4*4 .... 이런 것들만 있으니까 안되면 자르고 되면 넣고 하면 된다. 단순한 문제,

#include <iostream>
#include <vector>
using namespace std;

int cutting(vector<int> &ans, vector<vector<int>> paper, int size);
int check(vector<vector<int>> paper, int size);
int main()
{
	int size;
	cin >> size;
	int cnt = 0;
	vector<vector<int>> arr(size+1);
	vector<int> ans(3);
	ans[0] = ans[1] = 0;
	for (int i = 0; i < size; i++)
	{
		arr[i] = vector<int>(size + 1);
		for (int j = 0; j < size; j++)
		{
			cin >> arr[i][j];
			cnt += arr[i][j];
		}
	}
	if (cnt == 0 || cnt == size * size)
	{
		if (cnt == 0)
		{
			cout << 1 << endl << 0;
		}
		else
		{
			cout << 0 << endl << 1;
		}
	}
	else
	{
		cutting(ans, arr, size);
	}
	for (int i = 0; i < 2; i++)
		cout << ans[i] << endl;
	return 0;
}

int cutting(vector<int>& ans, vector<vector<int>> paper, int size)
{
	int tmp = check(paper, size);
	if (tmp != 2)
	{
		ans[tmp]++;
		return 0;
	}
	else
	{
		vector<vector<int>> p1(size / 2), p2(size / 2), p3(size / 2), p4(size / 2);
		for (int i = 0; i < size / 2; i++)
		{
			p1[i] = vector<int>(size / 2);
			p2[i] = vector<int>(size / 2);
			p3[i] = vector<int>(size / 2);
			p4[i] = vector<int>(size / 2);
			for (int j = 0; j < size / 2; j++)
			{
				p1[i][j] = paper[i][j];
				p2[i][j] = paper[i + size / 2][j];
				p3[i][j] = paper[i][j + size / 2];
				p4[i][j] = paper[i + size / 2][j + size / 2];
			}
		}
		cutting(ans, p1, size / 2);
		cutting(ans, p2, size / 2);
		cutting(ans, p3, size / 2);
		cutting(ans, p4, size / 2);
	}
	return 0;
}

int check(vector<vector<int>> paper, int size)
{
	int cnt = 0;
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
			cnt += paper[i][j];
	}
	if (cnt == 0)
	{
		return 0;
	}
	else if (cnt == size * size)
	{
		return 1;
	}
	else
		return 2;
}

알고리즘 오랜만에 푸니까 좋았다. 매 주 목요일 금요일은 알고리즘 공부 날이다.