[Python] 프로그래머스 LV.03 - 거스름돈

programmers.co.kr/learn/courses/30/lessons/12907

코딩테스트 연습 - 거스름돈

[ 알고리즘 ]
DP

[문제 접근]
코드는 굉장히 간단하지만, 이걸 생각해내기는 정말정말 쉽지 않음이 분명하다.
점화식을 한번에 찾아내기 어려웠던 문제, 개수로 따져서 그런 것 같다

간단히 설명해보자면.. dp[0] 은 아무것도 포함하지 않을 때, 즉 자기 자신만을 이용해 만들 수 있는 경우이다.

예시의 n=5, money=[1,2,5] 로 생각해보자

초기 상태의 dp=[1,0,0,0,0,0]

<1> money == 1 일때의 for문안에서 일어나는 일 ( = 즉, 1만 가지고 있을 때 만들 수 있는 것들)

i=1~5까지 순차적으로 증가하며,

dp[1]+=dp[1-1] # 자기 자신
dp[2]+=dp[1-2] # 5까지 모두 1로 채워진다 (1을 여러번 사용하면 1*n의 형태로 모두 하나씩 만들 수 있음)
...

<2> money==2 일때

i=2~5까지 순차적으로 증가하며,

dp[2]+=dp[2-2] #자기 자신 하나로 2를 만들 수 있음
dp[3]+=dp[3-2] # 1과 2를 가지고 만들 수 있음
dp[4]+=dp[4-2] # 2 를 가지고 만들 수 있음
dp[5]+=dp[5-2] # 3,2를 가지고 만들 수 있음

<3> money ==3 일때

i=3~5

dp[3]+=dp[3-3] # 위와 같이 자기자신으로 3을 만들 수 있음
dp[4]+=dp[4-3] # 1과 3으로
dp[5]+=dp[5-3] # 2와 3으로

.

.

.

<5> money ==5 일때
i=5

dp[5]+=dp[5-5] # 5를 이용하여 자기 자신만 만들 수 있으므로 이렇게 끝이난다.

[코드]

def solution(n, moneys): answer = 0 dp=[0]*(n+1) dp[0]=1 # 다른 것들이 0개 있을 때 = 즉, 자기 자신만 있을 때 for money in moneys: for i in range(money,n+1): # 해당 money까지 존재할때.. 해당 money 부터 끝까지 업데이트 dp[i]+=dp[i-money] return dp[n]% 1000000007