[백준 2482: JAVA] 색상환 / 동적 프로그래밍

개요

 

dp로 문제를 풀 수 있다.

이 문제는 dp를 생각하면 금방 풀이할 수 있지만, 약간의 조건이 추가되어 있기 때문에 생각을 좀 해야 했다.

한 칸씩 떨어져 있어야 하고 첫 색과 마지막 색도 떨어져야 하기 때문에 조금 까다로워 보일 수 있다.

 

dp는 일반적으로 이전의 값들을 이용하여 현재 원하는 값을 도출해내는 방식이기 때문에

어떻게 값을 도출해낼지 점화식을 만들어 보면 다음과 같다.

1~n번째까지 색이 있다면, n번째 색을 선택한 경우 + n번째 색을 선택하지 않은 경우로 구할 수 있다.

이걸 생각하고 문제를 풀어보자.

 

문제

 

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

그림 1. 먼셀의 20색상환

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

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

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

 

입력

 

풀이

 

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

 

1~n번째까지 색이 있다면, n번째 색을 선택한 경우 + n번째 색을 선택하지 않은 경우로 구할 수 있다.

 

위와 같이 n번쨰 색을 선택한 경우 → n - 1번째 색은 선택하지 못하므로 dp[n - 2][k - 1]이 된다.

 

 

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

 

그렇다면 dp[n][k] = dp[n - 2][k - 1] + dp[n - 1][k] 가 된다.

 

 

 

 

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

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

 

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

 

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

 

 

 

코드

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++){
            // i개 중에서 1개를 선택하는 방법은 i개이다.
            dp[i][1] = i;
            // 0개를 선택한 경우는 1로 초기화한다.
            // 점화식을 위해서는 1로 초기화해야한다.
            dp[i][0] = 1;
        }

        // i가 3미만인 경우는 계산할 필요가 없다.
        for(int i = 3; i <= n; i++){
            // n개의 수 중 n/2개 보다 더 많이 고르는 경우는 0가지이다.
            // 그렇기 때문에 j의 범위를 다음과 같이 설정한다.
            for(int j = 2; j <= (i + 1) / 2; j++){
                // i번째 색을 선택하지 않은 경우 + i번째 색을 선택한 경우
                dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % MOD;
            }
        }

        // n번째 색을 선택한 경우 + n번째 색을 선택하지 않은 경우
        bw.write((dp[n - 3][k - 1] + dp[n - 1][k]) % MOD + "\n");
        bw.close();
        br.close();
    }

}