[Gold V] 동전 2 - 2294

문제 링크

분류

다이나믹 프로그래밍

문제 설명

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이 (동적프로그래밍 - 바텀 업)

시간 복잡도 O(n) 공간 복잡도 O(n)

가치의 합에 대한 코인의 필요 갯수를 저장해두는 dp[] 배열을 사용해서 1~k까지의 반복을 통해 코인의 필요 갯수를 재갱신하여 풀었다.

j 원을 만들기위한 방법 = 기존에 갱신한 j원을 만드는데 필요한 동전의 수 vs j-n원을 만들기 위한 동전의 수 + n원 짜리 동전 하나

import java.io.*;
import java.util.*;

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    static final int INF = (int)10e9;

    public static void main(String[] args)throws IOException {
        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+1];
        for(int i=1; i<=n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[k+1];
        Arrays.fill(dp, 100001);  // Impossible value
		// 0원을 만드는데 필요한 코인 수는 0개
        dp[0] = 0;
        for(int i=1; i<=n; i++) {
            for(int j=coins[i]; j<=k; j++) {
                dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);
            }
        }

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