[백준 c++] 2482 색상환

문제

https://www.acmicpc.net/problem/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) 으로 나눈 나머지를 출력한다.

풀이

1. dp 설계

1~ n개의 색상 중 0~k개를 선택하는 경우의 수를 저장

dp[색상 수][선택한 수]
dp[i][0] = i개 색상 중 0개 선택하는 경우의 수 = 1
dp[i][1] = i개 색상 중 1개 선택하는 경우의 수 = i

2. 점화식 세우기

dp[n][k] = dp[n-2][k-1] + dp[n-1][k]

3.

   for (int i = 2; i <= n; i++)
        for (int j = 2; j <= k; j++)
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % mod;

4.

(dp[n - 1][k] + dp[n - 3][k - 1]) % mod;

1) n번째 색을 선택하지 않는 경우
= n-1개 색상 중 k개 선택하기


2) n번째 색을 선택하는 경우
= 1번째 제외, n-1번째 제외, n번째는 이미 선택했다 치고 제외
=> n-3개 색상 중 k-1개 선택하기

코드

#include <iostream>
#include <algorithm>
#define mod 1000000003;
using namespace std;
int n, k;
int dp[1001][1001];

int main()
{
    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        dp[i][0] = 1;
        dp[i][1] = i;
    }

    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= k; j++)
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % mod;

    cout << (dp[n - 1][k] + dp[n - 3][k - 1]) % mod;
}