[더블릿 - 3] 색상 환/color_circle

프로그램 명: color_circle

제한시간: 1 초

색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다.

미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 그림은 먼셀의 20색상환을 보여준다.

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

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

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

입력

입력의

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

출력

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

입출력 예

입력

4
2

출력

2

출처: koi 지역중등

이 문제는 간단한 조합식으로 나타낼 수 있다.
사용된 식을 말로 쓰면
N개의 색 중에서
K개를 선택하는데
이들은 서로 이웃하면 안된다.

따라서, 이 문제는 다음과 같이 생각할 수 있다.
N개를 한 줄로 세우는데 이웃하지 않는 K개를 선택하는 가지 수를 구하는 것으로 바꿔 생각 할 수 있다.
이는 한번도 바꿔 생각해보면
N개 중에서
일단 N-K개를 먼저 세워놓고
K개를 이들 사이에 넣는다고 생각하면 된다.

예를 들면
 1 1 1
(N이 5, K가 2라면)
 일단 N-K개를 세우면
0 1 0 1 0 1 0 
K개가 들어갈 수 있는 자리는 0으로 표현되는 4군데이다.
하지만, 이들은 색상환표인 원순열이므로 맨 왼쪽과 맨 오른쪽에 동시에 K를 넣으면 안된다.
따라서 맨 왼쪽에 K를 넣었을 때와, 안 넣었을 때를 구별해서 순열을 게산해보면

2C2 + 3C2

2C2는 맨 왼쪽을 선택했을 때로, 맨 오른쪽에는 넣을 수 없으므로
나머지 두 군데중에서 한군데를

3C2는 맨 왼쪽을 선택하지 않았을 때로, 이경우에는 맨 왼쪽을 제외한
다른 어느곳이든 괜찮다.
따라서 나머지 구간 중, 두개를 고르면 된다.

이것을 일반화 하면

N개를 일렬로 세우는데 K개가 서로 이웃하지 않는 경우는

로 나타낼 수 있다.

따라서, 순열을 구하는 함수를 만들고,
오버플로우를 방지하기 위해
매 곱셈마다 Mod 1,000,000,003 을 해주면 된다. 

#include
using namespace std;
#include
 
const int MOD = 1000000003;
/*
    Time Complexity: O(n*r)
    Space Complexity: O(r)
*/
long long C(int n, int r)
{
    vector< vector > C(2,vector (r+1,0));
 
    for (int i=0; i<=n; i++)
    {
        for (int k=0; k<=r && k<=i; k++)
            if (k==0 || k==i)
                C[i&1][k] = 1;
            else
                C[i&1][k] = (C[(i-1)&1][k-1] + C[(i-1)&1][k])%MOD;
    }
    return C[n&1][r];
}
 
int main()
{
    int n,r,s=0;
 
    scanf("%d%d",&n,&r);
    s = C(n-r-1,r-1) + C(n-r,r);
    printf("%d\n",s%MOD);
 
    return 0;
}