거스름돈

210703

'''
https://programmers.co.kr/learn/courses/30/lessons/12907
거스름돈
[풀이]
1. 각 코인에 대해서 반복문
=> 1부터 n까지 해당 코인이 n원을 이룰 수 있는지 검사
=> 예를 들어 dp[1] 은 n=1 일 때의 여러 코인을 가지고 구성할 수 있는 경우의 수
=> a원의 코인을 가지고 이야기 할 때,
=> dp[n+a]는 dp[n]에서 a원을 더한것이므로
=> 적어도 dp[n]을 구성하는 경우의 수만큼은 dp[n+a]에서도 존재할 것임 따라서 dp[n]을 더해준다.
=> 예를 들어 시작점에서 목적지까지 A길과 B길이 있고,
=> A길은 2갈래 길, B길은 3갈래 길이라면 총 갈 수 있는 방법은 5가지와 마찬가지.
=> dp[2+3]은 dp[2]에서 3원을 더한것이므로 dp[2]의 경우를 dp[5]에 더해주고
=> dp[4+1]은 dp[4]에서 1원을 더한것이므로 dp[4]의 경우를 dp[5]에 더해준다.
=> 핵심은 이 작업은 a원에 대해서 한다는 것
2. dp = [1] + [0] * n
=> price가 coin 보다 크거나 같을 때 더해주는 연산을 하는데,
=> 같을 때의 경우를 고려해준 것
=> dp[0+5]는 dp[0]에서 5원을 더한 것이다.
=> 이는 기본적으로 5원을 구성하기 위해 5원 자체로 존재하는 방법 1가지가 존재하므로
=> dp[0]을 1로 설정.
'''
def solution(n, money):
    dp = [1] + [0] * n
    for coin in money:
        for price in range(coin, n + 1):
            dp[price] += dp[price - coin]
    return dp[n] % 1000000007
'''
bfs 문제로 풀었더니 시간초과.
dp 로는 해결하지 못해서 다른 풀이 참조.
https://velog.io/@younge/Python-프로그래머스-거스름돈-연습문제DP
'''