[DP] 동전 교환 - 최소 개수

시간 제한: 1000 ms메모리 제한: 256 MBSilver V3작성자: 관리자

$K$ 가지 동전이 있고 각 동전은 무한히 쓸 수 있다. 금액 $M$ 을 정확히 만드는 데 필요한 동전의 최소 개수를 구하라. 만들 수 없으면 $-1$ 을 출력한다.

$dp[m]$ 을 "원을 만드는 최소 동전 개수"라 하면, 마지막에 쓴 동전 하나를 빼고 본다.

문제 통계

5

전체 제출

2

정답

40%

정답률

2

정답자 수

m

$dp[m] = \min_{c \le m} \bigl(dp[m-c] + 1\bigr), \quad dp[0] = 0$

닿을 수 없는 금액은 무한대로 두고, 마지막에 $dp[M]$ 이 무한대면 $-1$ .

입력

첫 줄에 $K$ 와 $M$ ( $1 \le K \le 20$ , $1 \le M \le 10^4$ ). 둘째 줄에 동전 액면 $K$ 개 ( $1 \le c_i \le 10^4$ ).

출력

최소 동전 개수, 또는 $-1$ .

입력:
3 6
1 3 4
출력: 2