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

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12907

 

2. 코드

python 1

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

풀이

1. dp[i]를 금액 i를 만드는 경우의 수로 정의하고, dp[0] = 1로 초기화

→ 0원을 만드는 방법은 "아무 동전도 쓰지 않는 방법" 1가지

1. 동전 하나씩 반복하며 가능한 금액(i) 갱신
2. 각 coin에 대해 i를 coin 이상부터 n까지 탐색
   1. dp[i] += dp[i - coin]
   2. → 금액 (i - coin)에 coin 하나를 추가한 조합이 금액 i를 만드는 방법
3. 모든 동전에 대해 반복하면서 dp 테이블을 채움
4. 최종 n원을 만드는 경우의 수 출력

 

3. 메모

• 반복 계산하는 부분을 최소화 → DP사용해서 최소화 함
• 점화식을 어떻게 해야 하는지 고민해야 하는 문제
  • dp[i] = 금액 i를 만드는 경우의 수
  • dp[i] += dp[i - coin] : coin을 하나 더 붙이면 i원이 되는 구조
  • 조합 문제이므로 동전이 바깥 루프에 있어야 순서 중복 방지