ex) 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 주기 가능
1) 1원을 5개 사용
2) 1원을 3개 사용하고, 2원을 1개 사용
3) 1원을 1개 사용하고, 2원을 2개 사용
4) 5원을 1개 사용
n: 거슬러 줘야 하는 금액
money: Finn이 현재 보유하고 있는 돈의 종류
Finn이n 원을 거슬러 줄 방법의 수를 return
제한 사항
n은 100,000 이하의 자연수
화폐 단위는 100종류 이하
모든 화폐는 무한하게 있다고 가정
정답이 커질 수 있으니,1,000,000,007로 나눈 나머지를 return
"""
입출력 예시)
n = 5, money = [1,2,5] -> 4
"""
## 의사코드 ##
# DP -> 점화식 찾기
# 제일 작은 화폐부터 사용
# 빈 리스트 생성
# dp = [0] * n+1
# money 내에서 반복
# for coin in money:
# 현재 선택한 coin으로 n원 이하까지의 금액(price)을 만들 수 있는 경우의 수를 dp에 저장
# for price in range(coin, n+1): # coin ~ n까지 반복
# if price >= coin: # price가 coin보다 작은 경우는 없음
# dp[price] += dp[price - coin] # dp[price] = (price - coin)원을 만들 수 있는 경우 각각에 coin을 더한 것
# 1,000,000,007로 나눈 나머지를 return
# return dp[n] % 1,000,000,007
통과한 코드
def solution(n, money):
# 빈 리스트 생성
dp = [0] * (n+1)
# 초기값 설정
dp[0] = 1
for coin in money:
for price in range(coin, n+1): # coin ~ n까지 반복
if price >= coin: # price가 coin보다 작은 경우는 없음
dp[price] += dp[price - coin] # dp[price] = (price - coin)원을 만들 수 있는 방법 각각에 coin을 더한 것
return dp[n] % 1000000007
-> 제일 작은 화폐부터 사용해서 해결하고, 그 값을 다음 큰 화폐를 사용할 때 재활용하므로 DP(동적 계획법) 이용
! dp[0]을 1로 설정하지 않으면 dp[price]가 업데이트되지 않음 !
'dp[price] = (price - coin)원을 만들 수 있는 경우 각각에 coin을 더한 것'의 의미
# money = [1, 2, 5]일 때 coin: 2, price: 4 인 경우
# => 1) 1+1+1+1
# => 2) 1+1+2
# => 3) 2+2
# 현재 dp[4] = 1
# -> coin: 1, price: 4 일 때 갱신된 값
# => 1+1+1+1
# price - coin: 2, dp[2] = 2
# => 1) 1+1
# => 2) 2
# dp[price] + dp[price - coin]
# => dp[4] + dp[4-2] = 1 + 2 = 3
# -> dp[4]: coin: 1, price: 4 일 때의 값으로 1원 동전만으로 4원을 만드는 경우의 수
# => 1) 1+1+1+1
# -> dp[4-2]: 1원 동전과 2원 동전으로 2원을 만드는 경우의 수
# => 1) 1+1
# => 2) 2
# 'dp[price] = (price - coin)원을 만들 수 있는 경우 각각에 coin을 더한 것'의 의미
# -> (4-2)원을 만들 수 있는 방법 각각에 coin(2)을 더한 것
# => 1) (1+1) + 2
# => 2) (2) + 2
