문제 설명 및 제한사항
아이디어 및 해결 방법
코드
# 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
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges