[백준 2482] 색상환 (C++)

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

2482번: 색상환

 

문제

---

색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.

 

색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.

주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자.  먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다.

주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

---

입력 파일의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4 ≤ N ≤ 1,000)이 주어지고, 둘째 줄에 N색상환에서 선택할 색의 개수 K(1 ≤ K ≤ N)가 주어진다. 

출력

---

첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.

 

문제 풀이

---

색상환이 원형이므로 끊어서 선형으로 만든다. 만약 첫번째 색을 선택한다면 두번째 색과 마지막 색을 선택할 수 없다. 남은  N-3개 중 K-1개를 어떤 두 색도 인접하지 않게 골라야 한다. 첫번째 색을 선택하지 않는다면 남은 N-1개 중 K개를 어떤 두 색도 인접하지 않게 골라야 한다.

n개 중 어떤 두 색도 인접하지 않고 r개를 선택하는 방법은 n-r개 색 사이사이에 r개 색을 끼워넣는 방법의 수와 같다. n-r+1개 중 r개를 선택해야 하므로 _n-r+1 C _r이 된다.

 

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int** dp = new int*[1001];
	long long answer = 0;
	for (int i = 0; i < 1001; i++)
	{
		dp[i] = new int[1001];
		for (int j = 0; j < 1001; j++)
		{
			dp[i][j] = 0;
		}
	}
	for (int i = 1; i< 1001; i++)
	{
		dp[i][0] = 1;
		dp[i][i] = 1;
		for (int j = 1; j < i; j++)
		{
			dp[i][j] = dp[i - 1][j] % 1000000003 + dp[i - 1][j - 1] % 1000000003;
			dp[i][j] %= 1000000003;
		}
	}
	int N, K;
	cin >> N>>K;
	if (N % 2 == 0 && K > N / 2)
	{
		cout << "0" << "\n";
	}
	else if (N % 2 == 1 &&  K >= (N / 2 + 1))
	{
		cout << "0" << "\n";
	}
	else
	{
		int a = N - 1;
		int b = K;
		if (N - K - b >= 0)
		{
			answer = dp[N - K][b];
		}
		int c = N - 3;
		int d = K - 1;
		if (N-K-1 -d >= 0)
		{
			answer += dp[N-K-1][d];
		}
		answer %= 1000000003;
		cout << answer << "\n";
	}
	return 0;
}