[JAVA] 백준 (골드5) 2294번 동전 2

링크

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

---

입력 예제

3 15
1
5
12

---

출력 예제

3

---

풀이

동전이 1, 5, 12원으로 주어지고, 합이 15원이 되도록 하는 경우의 수를 생각해보면

우선 1원을 사용했을 때는 다음과 같다.

• 1원: 1 -> 1개
• 2원: 1*2 -> 2개
• 3원: 1*3 -> 3개
  ...
• 15원: 1*15 -> 15개

그다음 5원을 사용한다면

• 5원: min(1*5, 5) -> 그냥 5원 1개만 사용하는 것이 최소
• 6원: min(1*6, 1+5) -> 1원에 5원을 추가하는 것이 최소
  ...
• 10원: min(110, 52) -> 5원을 만드는 경우의 수에 5원을 추가하는 것이 최소
  ...

결국 k원을 만드는 최소의 동전 개수는 k-coin원을 만드는 최소의 동전 개수에 coin원을 추가하는 경우가 된다.

dp배열은 다음과 같이 정의한다.

dp[i]: i원을 만들 수 있는 동전의 최소 개수

Bottom-Up 방식으로 DP를 구현하면 다음과 같다.

for (int coin : coins) {
    for (int i = coin; i <= k; i++) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[] coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        //dp[i]: i원을 만들 수 있는 동전의 최소 개수
        int[] dp = new int[k + 1];
        int max = 100_001;
        Arrays.fill(dp, max);
        dp[0] = 0;  //0원을 만드는 동전의 개수는 없다

        for (int coin : coins) {
            for (int i = coin; i <= k; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

        if (dp[k] == max) {
            System.out.println(-1);
        } else {
            System.out.println(dp[k]);
        } 
    }
}