[프로그래머스][DP] 거스름돈

거스름돈

프로그래머스

 

 

• 내 풀이
  • 중복을 막으려면, 동전 단위별로 바깥 루프를 돌려야 함.
  • 예를 들어 1,2,5 동전으로 5원을 만드는 경우의 수를 세려면,
    • 1원을 기준으로 다 만들고 → 2원을 추가해서 만들고 → 5원을 추가하는 순서로 진행해야 중복이 제거됨
  • 누적 DP: 앞의 수들을 만들 수 있는 방법의 수를 누적한 값

def solution(n, money):
    INF=1000000007
    
    dp=[0 for _ in range(n+1)]
    dp[0]=1
    
    for m in money: # 중복 방지하려면 한 화폐로 만들 수 있는 수 한 번씩만 체크
        for i in range(m,n+1):
            dp[i]=(dp[i]+dp[i-m])%INF

    return dp[n]