[Gold III] 색상환 - 2482

문제 링크

성능 요약

메모리: 20344 KB, 시간: 136 ms

분류

다이나믹 프로그래밍

문제 설명

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

그림 1. 먼셀의 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) 으로 나눈 나머지를 출력한다.

풀이 과정

점화식

dp(n, k) = dp(n-2, k-1) + dp(n-1, k)

1. n 번째 색을 선택한 경우	n번째 색을 선택한 경우 n - 1번째 색은 선택불가	dp(n-2, k-1)
2. n 번째 색을 선택하지 않은 경우	n번째 색을 선택하지 않는 경우 n - 1개 중에서 k개를 선택하는 경우	dp(n-1, k)

4개의 색이 있을때 4번째 색을 선택한 경우

위와 같이 n번째 색을 선택한 경우 → n - 1번째 색은 선택불가로 dp[n - 2][k - 1]이 된다.

4개의 색이 있을때 4번째 색을 선택하지 않은 경우

위와 같이 n번째 색을 선택하지 않는 경우 → n - 1개 중에서 k개를 선택하는 경우와 같으므로 dp[n - 1][k]가 된다.

원형 특성 반영

dp배열을 전부 채웠다면 정답을 구해야 한다.

원형의 특성을 반영하기 위해 첫 번째 색을 선택한 경우와 선택하지 않은 경우를 나누어 최종 답을 계산합니다.

dp[n - 3][k - 1] + dp[n - 1][k]) % MOD

정답도 n번째 색을 선택한 경우, 선택하지 않은 경우로 나뉜다.

n번째 색을 선택한 경우 1을 선택하면 안 되기 때문에 dp[n - 3][k - 1]과 같다.

n번째 색을 선택하지 않은 경우 1~9까지 중에 k개를 선택하는 경우와 같으므로 dp[n - 1][k]가 된다.

(i + 1) / 2하는 이유는?

[1, 2, 3, 4]

이 경우, 고를 수 있는 색은 3가지입니다: (1, 3), (1, 4), (2, 4)

배열이 4개일 때 최대 선택 가능한 색은 2개( (4 + 1) / 2 = 2 )

인접한 색을 선택할 수 없기 때문에 가능한 색을 선택할 수 있는 최대 개수를 구하기 위함입니다.

정답 코드(JAVA)

import java.io.*;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int MOD = 1_000_000_003;

    static int n, k;
    static int dp[][];

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        dp = new int[n + 1][n + 1];

        for(int i = 1; i <= n; i++){
            dp[i][0] = 1; //i개의 색 중 0개 선택 경우의 수 1가지
            dp[i][1] = i; //i개의 색 중 1개 선택 경우의 수 i가지
        }

        for(int i = 3; i <= n; i++){
            for(int j = 2; j <= (i + 1) / 2; j++){ //인접한 색 동시에 선택할 수 없음(최소 두 칸 이상 떨어짐)
                dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % MOD;
            }
        }

        bw.write((dp[n - 3][k - 1] + dp[n - 1][k]) % MOD + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}