[HackerRank][DP][파이썬] Coin Change Problem (Memoization 풀이법)

Problem

https://www.hackerrank.com/challenges/coin-change/problem

The Coin Change Problem | HackerRank

---

개인적으로 아주 어려웠다. 동전을 각 한개씩 사용할 수 있는 것이 아닌, 중복되서 사용되는 경우도 고려한 경우의 수를 나타내는 점화식을 도출해야 하기 때문이다.

 

Step 1. Optimal Structure 확인

 

주어진 문제 조건을 아래와 같이 정의하자.

 

\begin{align} &S = [S1, S2, ··· , Sm] \; (set\; of\; coins)  \\ &M \; = \; number \; of \; coins,\quad N \;=\;Target \; value, \\ &s_k \; is \; unique \; value \; (where \; 1 \leq k \leq m) &&  \end{align}  

 

이제, 주어진 문제의 최적해가 Subproblem으로부터 구해지는지 확인해보자.

목표값 $N = 100$ 을 $S = [50,25,10,5,1]$ 의 경우를 고려해보자.

 

붉은색 네모에 50과 25를 사용하여 50의 수를 만든 경우의 수를 고려하였을 때, 우리는 다시, 10, 5, 1의 숫자를 조합하여 나머지 50을 충족시켜야 한다. 이는, 최적해를 구하기 위해서는 Subproblem의 해를 포함해야 한다는 것을 직관적으로 알 수 있다.

 

Step 2. 점화식 찾기

해를 $f(S[ \; ],m,n)$ 로 정의하자. 여기서, $N = 5$ 에 대한 $S = [1,2,3]$ 의 경우의 수를 모두 구하였을 때 아래 그림과 같다.

 

이때, 최적해와 부분해와의 관계는 아래와 같이 만족한다는 것을 추론해야 한다.

$$ f(S[ \; ],m,n) = f(S[\;],m,n-S_m) + f(S[\;],m-1,n) $$

 

Step 3. 코드 구현

 

1차 시도. 재귀(Recursion)

Step 2에서 얻은 관계를 바탕으로 재귀(Recursion) 방식으로 접근해보자.

 

아래 방법은 해를 구하기 위해 2개의 부분 최적해를 구해야 하기 때문에 $O(2^n)$ 의 시간복잡도를 가진다.

def getWays(c,m,n):
    
    # 목표값 n = 0 인 경우, 아무 동전도 포함하지 않는 것을 1로 함
    if (n == 0):
        return 1

    # 목표값 n < 0 인 경우는 존재할 수 없음
    if (n < 0):
        return 0
    
    # 잔여 코인이 없는 경우 해가 존재하지 않음
    if (m<=0):
        return 0

    return getWays(c,m-1,n) + getWays(c,m,n-c[m-1])

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    m = int(first_multiple_input[1])

    c = list(map(int, input().rstrip().split()))

    # Print the number of ways of making change for 'n' units using coins having the values given by 'c'

    ways = getWays(c,m,n)

    fptr.write(str(ways) + '\n')

    fptr.close()

 

2차 시도. Dynamic Programming (Memoization)

얻은 점화식을 바탕으로 Top-Down 방식인 Memoization 방법으로 접근해보자.

 

재귀적으로 수행하다가 같은 정보가 필요할 때 일전에 구한 정답을 그대로 불러오면서 불필요한 계산을 줄일 수 있게 된다. 해당 풀이의 시간 복잡도는 $O(m*n)$ 의 시간복잡도를 가진다.

def getWays(c,m,n,dp):
    
    if n == 0:
        dp[m][n] = 1
        return dp[m][n]
    
    if n < 0:
        return 0
    
    if m <= 0 :
        return 0
    
    # 계산한 문제라면 그대로 반환
    if dp[m][n] != -1:
        return dp[m][n]
    
    # 관계식
    if c[m-1] <= n:
        dp[m][n] = getWays(c,m,n-c[m-1],dp) + getWays(c,m-1,n,dp)
        return dp[m][n]
    
    # 더 이상 경우의 수로 나누어 지지 않는 경우
    else:
        dp[m][n] = getWays(c,m-1,n,dp)
        return dp[m][n]


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    m = int(first_multiple_input[1])

    c = list(map(int, input().rstrip().split()))
    
    dp = [[-1 for _ in range(n+1)] for _ in range(m+1)]

    # Print the number of ways of making change for 'n' units using coins having the values given by 'c'

    ways = getWays(c,m,n,dp)

    fptr.write(str(ways) + '\n')

    fptr.close()

---

참조

https://www.youtube.com/watch?v=sn0DWI-JdNA&ab_channel=HackerRank 

https://www.geeksforgeeks.org/coin-change-dp-7/