[김태원 알고리즘] 동전교환 (냅색 알고리즘, DP)
사용 언어: Python3
문제
풀이
내 풀이 - 그리디
N = int(input())
lst = list(map(int, input().split()))
M = int(input())
ans = 0
lst.sort(reverse=True)
print(lst)
for x in lst:
ans += M // x
M %= x
if M == 0:
break
print(ans)
- 테스트 케이스 5개 중 4개만 통과한다
- 그리디는 최적의 해를 보장하지 않기 때문에 한 개를 통과하지 못한다.
다른 풀이 - DP 🌟
N = int(input())
lst = list(map(int, input().split()))
cost = int(input())
# dp : 거슬러줄 금액이 index일 때 동전의 최소 "개수"
dp = [1000] * (cost + 1) # ✅ 거스름돈은 최대 500 -> 모두 1원 -> 동전 500개 필요 -> 넉넉히 1000으로 초기화
dp[0] = 0 # ✅ 0원을 거슬러주는데 사용되는 동전의 수는 0개
for val in lst: # val은 동전의 종류
for j in range(val, cost + 1):
dp[j] = min(dp[j-val] + 1, dp[j])
print(dp[M])
- 정답!
💛 개인 공부 기록용 블로그입니다. 👻