교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 8 다이나믹 프로그래밍
실전문제 8-5 효율적인 화폐 구성 226p
N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.
입력 예시
2 15
2
3
출력 예시
5
난이도..무섭다.. DP... 어려워.. ㅠㅠ 결국 보고 풀었다.. 내일 다시풀어봐야겠다.. 알 수 없 어...정말로... 당분간 진짜 DP 파서 뽀개고 끝내던가 해야될 것 같다.. 이렇게 안일하게 하면 클난다...정말
n,m = map(int, input().split())
arr=[]
for i in range(n):
arr.append(int(input()))
d = [10001]*(m+1)
d[0]=0
for i in range(n):
for j in range(arr[i],m+1):
if d[j-arr[i]] != 10001:
d[j] = min(d[j], d[j-arr[i]]+1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
- 풀이시간 : /30분
이 문제 결국 이해하셨나요? 이코테 구글검색하면 항상 상단에 노출되서 자주 들어오게 되네요 원하는 바 이루셨길 바랍니다~ dp 어렵네요..