[HackerRank] The Coin Change Problem

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

The Coin Change Problem | HackerRank

 

 

< 문제 설명 >

사진과 같이 n과 c가 주어졌을 때, c로 n을 만들 수 있는 경우의 가지 수를 구하는 문제이다.

3을 만들 수 있는 조합이 저 3개인 것이다.

 

https://www.acmicpc.net/problem/2293

백준의 이 문제와 똑같은 문제!

 

 

< 문제 이해 >

기본적인 dp문제인데 조금 헤맸다.

dp[i] += dp[i-x] 의 식을 이용해서 풀고자 하였다.

 

 

< 시행 착오 >

위의 식을 사용하기 위해서 for문을 두번 사용했어야 했다.

배열 c를 돌리는 for문과 n번 돌아가는 for문.

그러나 두 개의 순서가 중요했다.

처음에 n번 돌아가는 for문을 먼저 작성했다가 중복되는 것들이 다 나와버려서 당황했다.

중복되지 않도록하려면 배열 c의 for문을 먼저 돌리면 된다.

 

 

< 문제 풀이 >

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

    for coin in c:
        for i in range(coin, n + 1):
            dp[i] += dp[i - coin]
    
    return dp[n]