프로그래머스 연습문제 - 거스름돈

문제 : 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]

참고

구글 각종 글