[Code Tree] 최대 동전 거슬러주기 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-max-coin-change/description

최대 동전 거슬러주기 설명 | 코드트리

 

---

풀이

문제 요약

종류 N개의 동전을 최대한 많이 사용해서 M을 만들자.

아이디어

금액 M에서 coin[j]을 뺀 금액을 만들 수 없는 경우가 존재한다. 이를 유의하며 coin[j - 1]를 만드는 수를 이용해 coin[j]를 만드는 수를 구하자.

점화식은 다음과 같다.

dp[i] : i를 만들기 위해 사용된 동전의 최대 갯수

dp[i] = max(dp[i], dp[i - coin[j]] + 1)

dp = [-1] * (M + 1)
dp[0] = 0
for i in range(1, M + 1):
    for num in coin:
        if i >= num and dp[i - num] != -1:
            dp[i] = max(dp[i], dp[i - num] + 1)

풀이 시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Trail-4-Intermediate-Low/DP I/23 최대 동전 거슬러주기(challenge-max-coin-change).py

problem-solving/code-tree/Trail-4-Intermediate-Low/DP I/23 최대 동전 거슬러주기(challenge-max-coin-change).py at main