[BOJ] 백준 2482 : 색상환 (java)

🧪 2482 색상환

---

난이도 : 🌟 골드 3
유형 : 동적 프로그래밍 (DP)

2482번: 색상환

 

📝 문제

---

색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(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) 으로 나눈 나머지를 출력한다.

 

🧐 핵심 로직

---

1) 맨 앞의 색상을 선택하는 경우 -> (n-3, k-1) 선택

2) 맨 앞의 색상을 선택하지 않는 경우 -> (n-1, k) 선택

 

원형의 경우는 n번째 색을 선택한 경우, 선택하지 않은 경우로 나뉜다. n번째 색을 선택한 경우 1을 선택하면 안 되기 때문에 dp[n - 3][k - 1] + n번째 색을 선택하지 않은 경우 1~9까지 중에 k개를 선택하는 경우와 같으므로 dp[n - 1][k]

 

즉, `dp[n][k] = dp[n - 3][k - 1] + dp[n - 1][k]`  

 

dp[i][j] = k ▶ i개의 색이 있을 때 j개의 색을 선택할 수 있는 경우의 수 = k

 

위의 상황을 DP로 처리하기 위해 "N개의 원소가 직선으로 놓인 상황에서 K개를 뽑는" DP 테이블 (dp[i-2][j-1] + dp[i-1][j]) 을 만든 후 원형에서의 정답인 dp[n-3][k-1] + dp[n-1][k] 를 구한다.

 

💻 최종 코드 (132 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    private static final int MOD = 1_000_000_003;

    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt")); 

        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        int[][] dp = getDp(n);

        if (k == 1) System.out.println(n);
        else System.out.println((dp[n-3][k-1] + dp[n-1][k]) % MOD);
    }

    public static int[][] getDp(int n) {
        int[][] dp = new int[n+1][n+1];
        dp[1][0] = 1;
        dp[1][1] = 1;

        for (int i=2; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                if (j == 1) dp[i][j] = i;
                else if (i > j) {
                    dp[i][j] = (dp[i-2][j-1] + dp[i-1][j]) % MOD;
                }
            }
        }

        return dp;
    }
}