BOJ 2294

2020-06-10

위 문제는 백준 사이트의 알고리즘 2294 문제에 관한 설명입니다.

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.

그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

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

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.

동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

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


import java.util.Scanner;

public class Coin2 {
    static int[] coin;
    static int[] sum;
    static int N;
    static int K;

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

        coin = new int[N + 1];
        sum = new int[K + 1];

        for (int i = 0; i < N; i++) {
            coin[i] = scanner.nextInt();
        }
        solve();
    }
    public static void solve(){
        for(int i=0; i<N; i++)
        {
            int current = coin[i];
            for(int j = current; j<=K;j++)
            {
                if(j==current){
                    sum[j]=1;
                    continue;
                }
                if((sum[j]==0 || sum[j]>= sum[j-current]+1) && sum[j-current]!=0) 
                    sum[j]= sum[j-current]+1;
            }
        }
        if(sum[K]!=0)
            System.out.println(sum[K]);
        else   
            System.out.println(-1);
    }
}

동전2