거스름돈 (파이썬)

문제 설명

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

프로그래머스

문제 풀이

• n이 10만이하, money 갯수는 100 이하 이므로 O(N^2)이 되더라도 1000만 이하라 효율성 테스트도 통과 가능
• 행을 money 요소로 열을 0~n 까지로 2차원 리스트를 생성
• 화폐 money[i]로 금액 j 를 만드는 방법은 아래와 같음
  • 이전까지 사용한 화폐들로 금액 j를 만든 방법 => dp[i-1][j]
  • 현재 금액 - 현재 화폐를 사용한 방법 => dp [i]  [ j-money[i] ]
    • eg. 1원만 있을 때 3원을 만든 방법은 딱 1가지다.  1 1 1
    • 이 후 2원이 주어졌을 때 이것으로 3원을 만드는 방법은 (3-2 , 2) 임 
    • 3-2 인 1은 이전 계산으로 1가지 인 것을 알고 있음. 
    • 따라서 2원을 사용해서 3원을 만드는 방법은 1
    • 1원과 2원으로 3원을 만드는 법은 (111, 12) 총 2가지 
• 점화식을 세우면
• 현재 구할려는 금액이 money[i] 보다 작을 경우에는 dp[i][j] = dp[i-1][j] 
• 현재 금액이 money[i] 이상 일 경우 dp[i][j] = dp[i-1][j] + dp[i][j-1] 

소스 코드

INF = int(1e9)+7

def solution(n, money):
    answer = 0
    m = len(money)
    dp = [[0]*(n+1) for i in range(m)]
    dp[0][0]=1
    for j in range(1,(n//money[0])+1):
        dp[0][j*money[0]]=1
                
    for i in range(1,m):
        for j in range(n+1):
            if j<money[i]:
                dp[i][j]=dp[i-1][j]
                continue
            dp[i][j]= dp[i-1][j]+dp[i][j-money[i]]
    
    for i in range(m):
        print(dp[i])
    

    answer=dp[m-1][n]
    
    return answer%INF

print(solution(5,[1,2,5]))