Programmers - 거스름돈 (파이썬)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12907
난이도 : 레벨 3

문제풀이

---

문제 정리

• 거슬러줄 돈 n을 주어진 money 배열을 가지고, 거슬러 줄 수 있는 방법의 모든 경우의 수를 찾아야 한다

분석

1. DP는 현재값이 어떻게 도출될지, 과거에 구해진 값을 참고하여 결정하는 방법이다.

   • 메모이제이션(Memoization)이라 한다.

2. 현재 문제도 유사한 점이 있는데, 과거에 도출된 값이 현재값에 영향을 미칠 수 있다는 점이다.

   • 제일 작은 코인부터 해당가격을 만들 수 있는 경우의 수를 구해서 저장한다
     1 = 1 ,
     2 = 1 + 1 ,
     3 = 1 + 1 + 1,
     4 = 1 + 1 + 1 + 1,
     5 = 1 + 1 + 1 + 1 + 1
     
     
   • 그 다음부터 현재 코인(coin)으로 부터 해당 가격(price)을 만들 수 있는 경우의 수를 구해준다.
     
     
   • 그 경우는 현재 가격(price)의 경우의 수와, 가격에서 코인을 뺀 값을 만드는 경우의 수(Price - Coin)를 더하면 될 것이다.

       for coin in money:
           for price in range(coin, n+1):
               dp[price] += dp[price - coin] 

   코인 / 가격	0	1	2	3	4	5
   1	1	1	1	1	1	1
   2	1	1	2	2	3	3
   5	1	1	2	2	3	4

   ex) 코인 2원이 가격 4원에 미치는 경우를 찾는방법
   - 4원은 1+1+1+1 로 가능하다 이전 분기의 dp[4]
   - 또한 4 - 2원의 조합으로 가능하다 dp[4 - 2]
   - dp[4 - 2] 이는 2원(이전코인으로 가능한 경우의 수) + 2원(코인)의 조합을 의미
   - 2 + 1 + 1
   - 2 + 2

3. 점화식은 다음과 같다.

   점화식 : dp[price] = dp[price] + dp[price - coin]

시간복잡도

• 시간복잡도는 $O(nm)$ 이다.
• 100 * 10만 = 1천만으로 여유있게 통과할 것이다.

전체코드

---

n = 5
money = [1,2,5]

def solution(n, money):
    dp = [0] * (n+1)
    dp[0] = 1
    for coin in money:
        for price in range(coin, n+1):
            dp[price] += dp[price - coin] 
    return dp[n] % 1000000007

print(solution(n, money))
# 4

정리 및 느낀점

---

• DP는 현재 값이 어떻게 결정되었는지 과거에 구해진 값을 통해 보기로 했다 (메모이제이션)
• 하지만 또한 현재 element가 어떻게 미래에 값에 영향을 미치는지 생각해 볼 수 있다.
• 알고리즘은 항상 정방향, 역방향 으로 구하는 방법에 대해 생각할 줄 알아야 한다.