[백준 알고리즘] 2294번 자바(Java) 동전2

조건

문제

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

 

입력

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

출력

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

 

풀이

시간복잡도를 보면 가치의 합 최대가 10,000 , 그리고 동전의 갯수 최대가 100개이다. 따라서

복잡도는 O(n*k), 즉 100만번이 최대이다.

 

새로운 동전이 들어올때마다 1~k원 까지의 가치의 합에 사용되는 동전갯수를 초기화해주면된다
식은   dp[i] = 기존dp[i]의 값과 dp[i-새로들어온 동전 값어치]+1 의 값과 비교하여 더 낮은 값을 대입해주면 된다.

dp[i] = Math.min(dp[i], dp[i-newCoin]+1) 

 

표로 보면 다음과 같다

 

 

 

예제 입력 예시

3 15
1
5
12

 

예제 출력 예시

3

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//2294번 동전 2

public class Main{
    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[] dp = new int[k+1];

        Arrays.fill(dp, 10001);
        dp[0] = 0;

        //dp
        for (int i = 0; i < n; i++) {
            int coin = Integer.parseInt(br.readLine());
            //동전의 가치가 k보다 크면 무시
            if(coin > k)continue;
            for (int j = coin; j <=k; j++) {
                dp[j] = Math.min(dp[j],dp[j-coin]+1);
            }
        }

        System.out.println(dp[k] == 10001 ? -1:dp[k]);
    }
}

 

 

 

 

문제 출처

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

2294번: 동전 2