백준 2482

문제

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

 

그림 1. 먼셀의 20색상환

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

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

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

 

풀이

숫자의 분할로 풀었다. 

색상환이 원형으로 되어있다는 점에 주의하고 풀면 된다.

서로 떨어져있는 K개의 색상의 경우의 수를 총 N개의 색상에서 뽑아야 하는 문제이다.

이를 그림으로 나타내면 (총 6개의 색상에서 3개를 선택하는 경우를 나타내면)

1. 무조건 첫번째 색을 선택하는 경우 (특정 색을 기준으로 선형으로 나타냈을때)

2. 무조건 마지막 색을 선택하는 경우 (특정 색을 기준으로 선형으로 나타냈을때)

3. 첫번째 색, 마지막 색을 선택하지 않는 경우

 

다음과 같이 세가지 케이스로 나눌 수 있다. (O가 색상 선택, X가 색상 비선택)

1, 3번 케이스는 N - K개의 색상을 무조건 K개의 숫자로 분할하는 경우

2번 케이스는 N - K 개의 색상을 무조건 K+1개의 숫자로 분할하는 경우이다.

모든 경우의 수를 다 더해주면 된다.

 

특정한 숫자를 K개로 분할하는 경우의 수는 DP를 통해 쉽게 구할 수 있다.

 

#include <iostream>
#define ll long long
#define MODNUM 1000000003
using namespace std;
ll N, K, dp[1001][1001];
int main() {
    cin>>N>>K;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) {
            if(i == j) dp[i][j] = 1;
            else {
                dp[i][j] = (dp[i-1][j] + dp[i-1][j-1])%MODNUM;
            }
        }
    cout<<(dp[N-K][K]*2 + dp[N-K][K+1])%MODNUM;
}