[코드트리 조별과제] 최대 동전 거슬러주기

https://www.codetree.ai/missions/2/problems/max-coin-change

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제는 사이트 들어가시면 볼 수 있습니다.

최대 동전 거슬러주기는 DP 문제로, 상태를 정의하는 것이 중요합니다. dp[i]를 이제까지 선택한 동전의 합이 i일 때 가능한 최대 동전의 개수라고 정의해보면, dp[i]에 이르기 위해 그 전 상황을 가정한 것을 그림으로 표현할 수 있습니다.

이렇게 표현할 수 있습니다. 그렇다면 dp[i]는 가능한 최대 동전의 개수이므로 dp[i] = max(dp[i], dp[i - coin[j]] + 1)이라는 점화식을 세울 수 있습니다. 여기서 j는 코인 리스트를 순회합니다. 최대 동전의 수를 구해야 하므로 dp 배열의 초기값은 매우 작은 값인 -sys.maxsize로 초기화했습니다. 그리고 0원은 초기값이 없으므로 dp[0] = 0입니다. 

import sys
n,m = map(int,input().split())
coin = list(map(int,input().split()))
INT_MIN = - sys.maxsize
dp = [ INT_MIN for _ in range(m+1)]
dp[0] =0

for i in range(1,m+1):
    for j in range(n):
        if i >= coin[j] and dp[i-coin[j]] == INT_MIN:
            continue
        if i >= coin[j]:
            dp[i] = max(dp[i],dp[i-coin[j]]+1)
print(dp[m] if dp[m] != INT_MIN else -1)​

돈을 거슬러 줄 수 없을 때는 -1을 출력하고, 그렇지 않으면 m원을 거슬러주는 동전의 최대 개수를 출력합니다.