[ BOJ ][JAVA][2294] 동전 2

www.acmicpc.net/problem/2294

2294번: 동전 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초 (추가 시간 없음)	128 MB	39396	11193	7744	28.165%

문제

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

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

입력

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

출력

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

예제 입력 1

3 15
1
5
12

예제 출력 1

3

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i, j, n=sc.nextInt(), k=sc.nextInt();
        int a[] = new int [n+1], d[] = new int[k+1];

        for(i=1;i<=k;i++) d[i] = 100001; d[0] = 0;

        for(i=1;i<=n;i++) a[i] = sc.nextInt();

        for(i=1;i<=n;i++)
            for(j=a[i];j<=k;j++)
                d[j] = Math.min(d[j], d[j-a[i]]+1);

        if(d[k]==100001) d[k] = -1;
        System.out.println(d[k]);

        sc.close();
    }
}