[python] HackerRank - The Coin Change Problem

문제

https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true 

The Coin Change Problem | HackerRank

---

접근

dp를 이용한 풀이.

주어진 모든 동전의 경우를 하나씩 살피면서

1원부터 n원까지 만들 수 있는 경우의 수를 메모이제이션해가며 만들 수 있는 모든 경우를 구해준다.

 

---

코드

def getWays(n,c):
    dp = [0] * (n+1)
    dp[0] = 1
    c.sort()

    for coin in c:
        if n >= coin: # 만드려는 금액이 동전의 금액보다 작으면 만들 수 없기 때문에 볼 필요 없음.
            for i in range(1, n+1):
                if i-coin >= 0: # 1~n까지 중 동전의 금액을 뺐을 때 0보다 작으면 만들 수 없기 때문에 볼 필요 없음.
                    dp[i] = dp[i] + dp[i-coin]
    return dp[n]