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

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

2630번: 색종이 만들기

 

 

 

#include <iostream>
using namespace std;

int board[128][128];
int boardSize;
int blue=0, white=0;

bool isSameColor(int x, int y, int size)
{
	int color = board[x][y];
	for(int i=0; i<size; i++)
	{
		for(int j=0; j<size; j++)
		{
			if(board[x+i][y+j] != color)
			{
				return false;
			}
		}
	}
	return true;
}

void count(int x, int y, int size)
{
	if(isSameColor(x,y,size))
	{
		if(board[x][y] == 1)
			blue++;
		else
			white++;
	}
	else
	{
		count(x,y,size/2);
		count(x,y+size/2,size/2);
		count(x+size/2,y,size/2);
		count(x+size/2,y+size/2,size/2);
	}
}

void init()
{
	cin >> boardSize;
	for(int i=0; i< boardSize; i++)
	{
		for(int j=0; j<boardSize; j++)
		{
			cin >> board[i][j];
		}
	}
}

int main() {
	init();
	count(0,0,boardSize);
	cout << white << endl << blue;
	return 0;
}

 

 

문제는 사각형을 4개로 분할하여 정복하는 방법을 사용했다. 분할정복법을 처음으로 사용해서 해결하는 문제였지만 문제의 난이도가 쉬워 편하게 구현할 수 있었다. isSameColor 함수도 분할정복으로 구현하고 싶었는데 그러지 못해서 아쉬웠고 다음에 기회가 된다면 새롭게 구현해 보고 싶다.