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

문제 링크

 

생각보다는 어려웠던 문제.

사실 이런 유사 문제는 DP 아니면 BFS일 때가 많고, 그중에서도 어지간하면 DP일 때가 많기는 하다.

이 문제에 BFS가 안 통하는 이유는, 순서가 상관없는 조합 문제이기 때문이다.

 

아래의 그림은 2원과 3원으로 10원을 만드는 조합이다.

2와 3으로는 2+2+2+2+2, 2+2+3+3와 같이 총 두 가지의 방법으로 10을 만들 수 있는데, 이는 아래의 그림과 같이 표현된다.

 

이를 코드로 표현하면 다음과 같다:

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