[백준 2293] 동전 1 (Java)

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

2293번: 동전 1

접근 방법

DP문제로 우선 점화식을 도출해야했다.

 

동전의 가치가 a, b, c라고 할 때

합이 k가 되도록 하는 동전의 경우의 수는

(k-a)원이 되는 경우에 a를 더한 경우,

(k-b)원이 되는 경우에 b를 더한 경우,

(k-c)원이 되는 경우에 c를 더한 경우로 총 3가지 경우가 있을 수 있다.

 

이를 점화식으로 도출하면

DP[k] = DP[k - a] + DP[k -b] + DP[k -c]가 된다.

 

하지만 위 점화식을 적용하면 중복되는 경우까지 셈을 하게 된다.

(k = 5일 때, 1 + 2 + 2의 경우와 2 + 2 + 1인 경우 한번만 세야한다.)

 

a만 사용한 경우, a와 b를 사용한 경우, a와 b와 c 모두 사용한 경우로 나눠 차례로 계산을 해야한다.

 

dp[0] = 1으로 잡고 시작한다.

dp[0]은 0을 만드는 경우의 수로 해석될 수 있지만

dp[a - a]로 생각하면 a값을 구할 때 a라는 동전 하나만 사용된 경우로 볼 수 있다.

 

우선 a만 사용한 경우를 구한다.

dp[i] += dp[i - a]

1부터 k까지 a만 사용한 경우를 구해놓게 된 것이다.

 

이후 b의 경우로 넘어가는데, a를 사용한 경우에 b라는 동전을 하나 사용한 경우의 수를 추가하는 것과 같다.

마찬가지로 c의 경우에도 a,b를 사용한 경우에다가 c라는 동전을 사용한 경우의 수를 추가한 것과 같다.

이렇게 하면 중복되지 않고 경우의 수를 구할 수 있다고 한다.

(DP 넘나 어려운 것.. 매번 새롭다ㅠ 내 머리는 아직 다이나믹하지 못한 듯 하다)

 

 

소스 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[] coins = new int[n];

        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }

        int[] dp = new int[k + 1];

        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                if (j - coins[i] >= 0) {
                    dp[j] += dp[j- coins[i]];
                }
            }
        }

        System.out.println(dp[k]);
    }
}