[BaekJoon] 백준 2482번 색상환

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

2482번: 색상환

 

 

풀이 : 

N개의 색상환을 입력받았을 때 K 개를 선택할 수 있는 경우의 수를 구하는 문제

 

dp[i][j] = i 개의 색상환에서 j 개를 선택할 경우의 수

여기서 j 를 선택하는 경우와 선택하지 않는 경우로 나눌 수 있다. 

 

j 번째를 선택하는 경우

= dp[i-2][j-1] 

 

j 번째를 선택하지 않는 경우

= dp[i-1][j]

 

dp[i][j] = dp[i-2][j-1] + dp[i-1][j]

 

단 마지막에서

N 개의 색상환이 주어졌을 때

N-1, 1번째 색상환을 모두 배재해야하므로 N-3 으로 구해야한다. 

dp[N][K] = dp[N-3][K-1] + dp[N-1][K]

 

 

초기화는 1 ~ N개의 색상환이 주어졌을 때 1개만 선택하는 경우 1 ~ N 개의 값을 가진다.

K가 1일 경우 K-1이 성립되지 않으므로 따로 구해줬다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int K;
    static int dp[][];
    static int MOD = 1000000003;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());
        dp = new int[N+1][K+1];
        
        /*
            dp[i][j] = i 개의 색상환 중에서 j 개를 선택했을 때의 경우의 수
            j 번째를 칠했을 경우 = dp[i-2][j-1]
            안칠했을 경우 = dp[i-1][j]
         */
        
        for(int i = 1; i<=N; i++) {
            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;
            }
        }
        
        int result = (dp[N-3][K-1] + dp[N-1][K]) % MOD;
        
        if (K == 1) {
            result = N % MOD;
        }
        
        System.out.println(result);
    }
}