[알고리즘 잡스] 상자 꾸미기 (C++, 완전 탐색)

문제

 

면이 6개인 상자가 있다. 이를 여러 가지 색종이를 붙여 꾸밀려고 하는데, 단 조건이 있다. 인접한 면에 같은 색의 색종이를 붙이면 안 된다는 것이다. 또한, 한 면에는 한 장의 색종이만 붙일 수 있다. 여러 가지 색의 색종이들이 주어졌을 때, 조건을 만족하여 상자의 모든 면에 붙일 수 있는지 판별하는 프로그램을 작성하시오.

 

입력

첫째 줄에 색종이의 장수 N ( 1 <= N <= 1,000 ) 이 주어진다. 둘째 줄에 각각의 색종이의 색깔을 나타내는 N개의 숫자가 주어진다. 색깔은 양의 정수로 이루어져 있고, 1부터 N까지의 범위의 수이다.

 

출력

조건을 만족하면서 상자를 꾸밀 수 있으면 “YES”, 아니면 “NO”를 출력한다.

 

---

#include <iostream>
#include <vector>

using namespace std;

int main() {

	int n;
	cin >> n;

	vector<int> arr(n+1, 0);
	
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		arr[tmp]++;
	}

	int cnt = 0, cnt2 = 0;

	for (int i = 1; i <= n; i++) {
		if (arr[i] >= 2) {
			cnt++;
			continue;
		}
		
		if (arr[i] >= 1)
			cnt2++;
	}

	if (cnt >= 3 || cnt2 >= 6 || (cnt >= 2 && cnt2 >= 2) || (cnt >= 1 && cnt2 >= 4)) 
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

완전 탐색으로 가능한지 확인하는 방법입니다. 여러 탐색 기법이 있지만 이 문제에서는 완전 탐색의 효율도 나쁘지 않습니다. 오히려 로직이 단순해서 더 빠를수도 있겠군요.

 

정육면체에 인접한 면에 색이 겹치지 않게 붙히는 방법은 총 4가지가 있습니다.

1. 다른 색종이를 1개씩 6개를 보유한 경우 ( 빨, 주, 노, 초, 파, 남, 보 )

2. 다른 색종이를 2개씩 3개를 보유한 경우 ( 빨, 빨, 노, 노, 남, 남 )

3. 다른 색종이를 2개씩 2개를 보유하고, 1개씩 2개를 보유한 경우 ( 빨, 빨, 주, 주, 노, 초 )

4. 다른 색종이를 2개씩 1개를 보유하고, 1개씩 4개를 보유한 경우 ( 빨, 발, 주, 노, 초, 파, 남 )

 

따라서, 각각의 색종이의 갯수를 배열 또는 벡터의 인덱스를 활용하여 저장하고, 해당 인덱스의 값이 1, 2 이상인지 검사하여 갯수를 저장하는 방식으로 탐색하고 나서, 위 4가지 조건 중 하나라도 가능하다면 "YES"를 출력하고, 조건이 하나도 해당되지 않는다면 "NO"를 출력합니다.