title: "[프로그래머스] 거스름돈 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/12907"
description: "프로그래머스 Level 3 문제 [거스름돈]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

# DP로 풀되, DP matrix 채우는 순서에 아이디어가 있습니다.
# cache[n] = n원을 만드는 경우의 수
cache = [1] + [0] * 100000

def solution(n, money):
    for coin in money:
        for price in range(coin, n + 1):
            # price-coin을 만들 수 있으면 이 coin 하나 더해서 price를 만들 수 있다.
        	cache[price] += cache[price-coin]
            
    return cache[n] % 1000000007

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges