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

문제

주어진 금액을 만들기 위해 동전 종류에 따라 거스름돈을 주는 방법의 수를 구하는 문제이다.

풀이

• 동적 프로그래밍(DP)을 사용해 풀 수 있다.
• 특정 금액 n을 만들기 위한 방법의 수를 누적해서 계산한다.
• 이때 작은 동전(금액)부터 시작해 큰 동전에 대해 가능한 경우의 수를 차례로 계산한다.
• dp[0]은 항상 아무 동전도 쓰이지 않는 방법 한 가지만 존재함으로 dp[0]=1로 지정한다.
• 현재 금액 x를 만들기 위한 방법의 수는 x - coin을 만들 수 있는 방법의 수에 현재 동전 coin을 추가한 것이다.

동전 1로 거슬러 주는 방

동전 1,2,5로 거슬러 주는 방법

• 이를 토대로 점화식을 구성하면 dp[x] = dp[x] + dp[x-coin] 이 된다.
• 마지막 정답을 도출할 때는 숫자가 매우 커질 것을 방지해 1000000007로 나눈 나머지를 반환한다.

Python 코드

def solution(n, money):
    dp = [0]*(n+1)
    dp[0] = 1

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

    return dp[-1]

 

문제출처

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