문제
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
우선 다이나믹 프로그래밍을 이용해서 푸는 문제였다.
처음에 아이디어를 떠올리는 것이 어려웠다..
예시로 3원짜리 동전을 하나 선택해서 10원을 만드는 동전의 최소 갯수는
7원을 만드는 최소 갯수 + 3원짜리 동전 1개인 것이다.
따라서 a원짜리 동전을 포함해서 k원을 만든다 했을 때
dp[k]=dp[k-a]+1 인 것이다.
n,k=map(int,input().split())
coin=[]
for i in range(n):
coin.append(int(input()))
dp=[10001]*(k+1)
dp[0]=0
for i in coin:
for j in range(i,k+1):
dp[j]=min(dp[j],dp[j-i]+1)
if dp[k]==10001:
print(-1)
else:
print(dp[k])
