문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12907
접근
동적계획법을 활용한 bootom-up 방식으로, 값이 올라갈수록 해당 경우의 수를 갱신하여 계산하고자 함
시행착오 - 금액을 기준으로 접근
처음에는 dp[n] 배열을 선언하고, 다음과 같이 money배열을 순회하면서 해당 배열의 인덱스값을 갱신해주는 방법을 선택하였다
for m in money:
dp[i]+=dp[i-m]
# 왜냐하면 동전이 1,2,5원이 있다고 가정할때,
#10원을 내는 경우의 수는 5원을 만드는 경우의 수에 5원짜리를 낸것+
#8원짜리 경우의 수에 2원짜리 낸것 +
#9원짜리 경우의 수에 1원짜리 낸 것과 같기 때문
#근데 이 생각은 굉장히 안일한 생각이었다.하지만 위 로직은 잘못 되었는데, 왜냐하면 각각의 경우마다 중복된 경우를 제거하지 않았기 때문이다. 예를들어 1원 2원을 활용하여 4원을 만든다고 할때, 해당 로직은 dp[3]+dp[2]로 계산된다. 하지만 각각의 경우를 살펴보면
3을 만드는 경우의 수
1,1,1 +1
1,2 +1
2,1 +1
2를 만드는 경우의 수
1,1 +2
2 +2
위 경우처럼 중복이 발생한다. 즉 이 방법은 폐기되어야 함
해결 - 동전 갯수를 기준으로 접근
중복인 경우를 배제하면서, 이전 결과에서 현재 결과를 도출하는 식을 찾아야한다
먼저 1원 동전만을 사용해서 1원~n원을 거슬러주는 경우의수는 모두 1이다
1
1,1
1,1,1
1,1,1,1....
여기서 2원 동전을 포함하여 거스름돈을 주는 경우의수는 다음과 같다
1원 : 1
2원 : 1+1, 2
3원 : 1+2, 1+1+1
4원 : 1+1+1+1, 2+1+1, 2+2
5원 : 1+1+1+1+1, 2+1+1+1, 2+2+1
즉 n원을 1원과 2원으로 거슬러주는 경우의 수는,
n을 1원만으로 거슬러주는 경우의 수 + n-2원을 1원만으로 거슬러주는 경우의 수 + n-4를 1원만으로 거슬러주는 경우의 수.... 등으로 표현할 수 있다
여기에 5가 추가된다면
이와 비슷하게 n원을 1원과 2원만으로 거슬러주는 걍우의 수+ n-5원을 1원과 2원만으로 거슬러주는 경우의 수, ..으로 표현할 수 있다.
이를 코드로 옮기면 다음과 같아짐
전체 코드
def solution(n, money):
dp=[0]*(n+1)
for mo in money:
for i in range(1,n+1):
if i==mo: # money에 포함되는건 일단 1을 더해주어야함
dp[i]+=1
elif i>mo:
dp[i]+=dp[i-mo]
dp[i]=dp[i]%1000000007
return dp[-1]
참고
구글 각종 글
