상자 꾸미기

문제

 

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

 

입력

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

 

출력

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

 

예제 입력

6

1 2 1 2 1 3

 

예제 출력

NO

 

예제 입력

6

1 2 3 1 2 3

 

예제 출력

YES

 

예제 입력

7

1 1 1 2 2 3 3

 

예제 출력

YES

 

예제 입력

8

1 2 2 2 1 1 1 3

 

예제 출력

NO

 

------------------------------------------------------------------------------------------------------------------------------

 

면에 겹치지 않으려면 최대로 가질 수 있는 한 가지 색의 색종이의 갯수는 2개이다. 3개가 될 경우 6개의 면을 가진 상자에 어떤 식으로든 겹치기 때문이다. 따라서 입력을 받은 뒤, 색깔의 범위는 1부터 N까지라고 정해져 있으니 색깔번호배열에 하나씩 더해서 넣어준다. 그리고 색깔번호배열의 값이 3이상, 즉 2를 초과할 경우 2로 정해준다. 그리고 색깔배열 값들을 모두 더했을 때, 6 미만이 나오는 경우는 "NO", 그렇지 않은 경우는 "YES"를 출력해주었다.

#include <iostream>
using namespace std;

int main()
{
	int n;
	int arr[1010] = { 0, };
	int numarr[1010] = { 0, };
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < n; i++) {
		numarr[arr[i]]++;
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		if (numarr[i] > 2) {
			numarr[i] = 2;
		}
		sum += numarr[i];
	}
	if (sum < 6) cout << "NO";
	else cout << "YES";
	return 0;
}