[김태원 알고리즘] 동전교환 (냅색 알고리즘, 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])

• 정답!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기