[Java] 백준 2482 색상환

https://www.acmicpc.net/problem/2482

2482번: 색상환

문제 조건

- 시간 제한 : java 기준 1초 

- 메모리 제한 : 128MB

- 정답 비율 : 35%

문제 설명 

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

 

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

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

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

 

접근 방법

DP를 사용해서 푼다. 

핵심 

1.  6가지의 색이 있다고 하면 1을 골랐을 때 6은 고르면 안 된다. (붙어 있다)

2. 골라야 하는 숫자가 N색상환 / 2 보다 더 크면 무조건 경우의 수는 0이다.  (n / 2 < k)

3. DP[i][j] 가 i까지 j개의 색을 고른다고 하면 DP[i][j] = DP[i-1][j] + DP[i-2][j-1] 이다. 

 

DP[i-1][j] 는 이번 i번째 색을 선택 안 하는 상황을 더하는 거고 

DP[i-2][j-1]는 이번 i번째 색을 선택하는 상황이다.

 

4. 2개의 배열을 만들고 DP1은 1을 사용하는 배열 DP2는 1을 사용 X 하는 배열

마지막 n번째 마지막 색을 고를 때는 DP2 에서의 값을 더한다. (1을 사용하지 않는 배열의 누적 경우의 수)

 

정답 코드 

import java.io.*;
public class Main {
    static final long INF = 1000000003;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        if(n / 2 < k){
            System.out.println(0);
            return;
        }
        long [][] DP1 = new long[n+1][k+1]; // 1을 사용 o
        long [][] DP2 = new long[n+1][k+1]; // 1을 사용 x
        for (int i = 1; i <= n; i++) {
            DP1[i][1] = 1;
            if(i == 1) continue;
            DP2[i][1] = 1;
        }
        for (int i = 3; i <= n; i++) {
            if(i != n){
                for (int j = 2; j <= k; j++) {
                    DP1[i][j] = (DP1[i-2][j-1] + DP1[i-1][j]) % INF;
                    DP2[i][j] = (DP2[i-2][j-1] + DP2[i-1][j]) % INF;
                }
            }
            else{
                for (int j = 2; j <= k; j++) {
                    DP1[i][j] = (DP2[i - 2][j-1] + DP2[i-1][j]) % INF;
                }
            }
        }
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += DP1[i][k];
            sum %= INF;
        }
        System.out.println(sum);
    }
}