[백준 / 골드4] 2482 색상환 (Java)

문제 보기

사용한 것

• N개의 색상 중 K개를 뽑는 경우의 수를 구하기 위한 bottom-up

풀이 방법

• dp[i][j]는 i개의 숫자 중 j개 뽑은 경우의 수를 나타낸다.
• dp[i][j]는 다음의 합과 같다.
  • dp[i - 1][j] : i - 1 개의 숫자 중 j 개 뽑은 것 (전 순서에서 뽑았음)
  • dp[i - 2][j - 1] : i - 2 개의 숫자 중 j - 1 개 뽑은 것 (이번 순서에서 뽑음)
• k > n/2인 경우엔 경우의 수가 존재하지 않는다.

코드

public class Main {

    private static final int MOD = 1_000_000_003;
    private static int n;
    private static int k;

    public static void main(String[] args) throws IOException {
        init();
        System.out.println(findNumberOfCases());
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        br.close();
    }

    private static int findNumberOfCases() {
        if (k > n / 2) {
            return 0;
        }
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][1] = i;
        }
        for (int i = 4; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % MOD;
            }
        }
        return dp[n][k];
    }
}