10주차 스터디 준비

주제 : 다이나믹 프로그래밍

 

내 문제 : 동전1_2293

2293번: 동전 1

 

dp[i] = i원을 만드는 경우의 수

coin[j] = 각 코인의 값

 

우선 1원만을 이용해서 값을 만드는 방법은 모두 1이다.

---

2원을 포함해서 값을 만드는 방법이다.

차이가 있는 부분은 원하는 값이 동전의 값(2원)이상일 때 생긴다.

2원 동전으로 2원을 만드는 경우는 한가지가 있으므로 1을 추가해준다.

3원을 만드는 경우는 1원동전으로 3을 만드는경우에 2원동전으로 (3-2원)1원을 만드는 경우를 더하면 된다. 

4원을 만드는 경우는 1원동전으로 4를 만드는경우에 2원동전으로 (4-2원)2원을 만드는 경우를 더하면 된다. 

---

10원을 만드는 경우는 1원동전으로 10을 만드는경우에 2원동전으로 (10-2원)8원을 만드는 경우를 더하면 된다. 

---

마지막으로 5원을 포함하여 값을 만드는 경우를 보면

마찬가지로 차이가 있는 부분은 원하는 값이 동전의 값(5) 이상인 경우 발생한다.

5원 동전으로 5원을 만드는 경우는 한가지가 있으므로 1을 추가해준다.

6원을 만드는 경우는 2원동전으로 4를 만드는경우에 5원동전으로 (6-5원)1원을 만드는 경우를 더하면 된다. 

1원동전으로 만드는 경우는 2원동전으로 만드는 경우에 포함되었기 때문에 따로 계산해주지 않아도 된다.

10원을 만드는 경우는 2원동전으로 10을 만드는경우에 5원동전으로 (10-5원)5원을 만드는 경우를 더하면 된다. 

 

점화식을 구하면

i가 coin[j]와 같다면 1을 증가시킨다.

i가 coin[j]보다 크다면

dp[i] = dp[i] + dp[i-coin[j]] 가 된다.

 

코드로 작성해보자

---

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

public class 동전1_2293 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str[] = br.readLine().split(" ");

        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);

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

        for (int i = 0; i < n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }

        for (int j = 0; j < n; j++) {
            for (int i = 1; i <= k; i++) {
                // 같은 경우에 1을 추가해준다.
                if (i==coin[j]){
                    dp[i]++;
                }
                // 그보다 큰 경우는 점화식을 적용한다.
                if (i>coin[j]){
                    dp[i] = dp[i] + dp[i-coin[j]];
                }
            }
        }
        System.out.println(dp[k]);
    }
}