[Baekjoon] 1780번: 종이의 개수

 

 

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

1780번: 종이의 개수

 

---

 

문제 해결 과정

착안

이전 포스트에서의 분할 정복(divide and conquer) 알고리즘 문제와 해결 방법이 유사하여 해당 코드를 변형하여 문제를 해결하였다. 정사각형 모양의 색종이가 균일한 색깔을 가지고 있는지 판단하여, 그렇지 않다면 가로를 3등분, 세로를 3등분한 다음, 동일한 크기의 9 개의 작은 색종이에 대해 다시 균일한 색깔을 가지는지 판단하는 과정을 반복하여 문제를 해결하고자 하였다.

 

구현

이전 포스트에서와는 달리, 문제에서 주어지는 종이의 최대 크기가 $3^7 \times 3^7$로 비교적 큰 편이므로, 메모리 절약을 위해 데이터를 char 형 배열로 저장하여 문제를 해결하였다. 편의상 -1인 종이를 0번 인덱스, 0인 종이를 1번 인덱스, 1인 종이를 2번 인덱스에 저장하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int N;
char Paper[2187][2187];
int Nums[3];

bool IsHomogeneous(int x, int y, int len)
{
	for (int i = y; i < y + len; i++)
		for (int j = x; j < x + len; j++)
			if (Paper[y][x] != Paper[i][j])
				return false;

	return true;
}

void Partition(int x, int y, int len)
{
	if (IsHomogeneous(x, y, len))
		Nums[Paper[y][x]]++;
	else
	{
		len /= 3;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				Partition(x + i * len, y + j * len, len);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			int c;
			cin >> c;
			Paper[i][j] = c + 1;
		}

	Partition(0, 0, N);

	for (int num : Nums)
		cout << num << "\n";

	return 0;
}

 

실행 결과