[Python] 프로그래머스 Lv 3 - 거스름돈

프로그래머스 Lv 3 거스름돈 문제 풀이

출처

 

알고리즘

단순히, 큰 거부터 고르면 큰일난다. 왜냐면, 돈의 종류에 대해서 제한이 없기에, 작은 돈의 배수가 money중에 있을 수 있 으며, 이의 경우 경우의 수가 달라진다!

따라서, 그리디로 푸는 것은 불가능. 

이 문제는 다른 방법으로 풀어야 할 것이다. 그 방법은 바로 DP.

동전이 1개인 경우, 2개인 경우, 3개인 경우로 늘려야 한다.
간단한 방식인데, 동전이 2개로 해결되는 경우와 그 동전이 꼭 필요한 경우를 나눠서 합치면 된다.

예시) 1,2,5원에서   13원 의 경우의 수를 구할려면
(1, 2원으로만 13원을 만드는 경우의 수) + (5원을 끼고 1,2,5원으로 13원을 만드는 수)

= (1, 2원으로만 13원을 만드는 경우의 수) + (5원 1개는 필수도 들어가고 1,2,5원으로 8원을 만드는 수)

이런식으로 점화식을 짜면, 중복 없이 모든 경우의 수를 넣을 수 있다.

 

코드

def solution(n, money):
    money_table = [[0 for _ in range(n+1)] for _ in range(len(money))]
    sorted(money)
    for curr in range(len(money)):        
        for i in range(0, n+1):
            if i == 0:
                money_table[curr][i] = 1
            else:
                if curr == 0:
                    if i % money[curr] == 0:
                        money_table[curr][i] = 1
                else:
                    if i < money[curr]:
                        money_table[curr][i] = money_table[curr-1][i]
                    else:
                        money_table[curr][i] = money_table[curr-1][i] + money_table[curr][i-money[curr]]
    return money_table[curr][n]