Programmers / 거스름돈 - 다이나믹프로그래밍(dp) / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 거스름돈 (3단계) 다이나믹프로그래밍

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12907

프로그래머스

문제 설명

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

• 1원을 5개 사용해서 거슬러 준다.
• 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
• 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
• 5원을 1개 사용해서 거슬러 준다.

거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• n은 100,000 이하의 자연수입니다.
• 화폐 단위는 100종류 이하입니다.
• 모든 화폐는 무한하게 있다고 가정합니다.
• 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

---

입출력 예nmoneyresult

5

[1,2,5]

4

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

---

나의 풀이 (첫번째 시도, itertools 이용)

from itertools import combinations_with_replacement
def solution(n, money):
    answer = 0
    set_list = list()
    for i in range(1,n+1):
        for coins in combinations_with_replacement(money,i):
            if sum(coins) == 5:
                if coins not in set_list:
                    answer += 1
        
    return answer % 1000000007

dp문제는 결국 점화식을 어떻게 잘 세우느냐가 관건이다... 더 공부해야겠군

 

일단 전형적인 돌다리 건너기, 계단 오르기에서 조금 더 심화된 문제이다.

타켓 금액만큼 길이의 dp리스트를 만들어주고 맨앞 0번째 인덱스의 값은 1로 채운다.

(이건 default)

 

 

1원 짜리 화폐 계산.

 

인덱스012345

	0	1	2	3	4	5
dp	1	0+1=1	0+1=1	0+1=1	0+1=1	0+1=1

1원 화폐를 계산하게 되면, 위와 같이 순서대로 값이 갱신 되어 전부 1이 될 겁니다.
1원일 경우 1원 1개만 내면 됩니다. 남은 돈은 0원이므로 0번 인덱스의 1을 더해줍니다.

2원일 경우 1원을 1개 내면 1원이 남습니다. 1원을 내는 경우의 수는 방금 계산한 값입니다. 1이 됩니다. 1을 더해주어 값이 1이 됩니다.
3원일 경우 1원을 1개 내면 2원이 남습니다. 2원을 내는 경우의 수는 방금 계산했습니다. 1을 더해주어 값이 1이 됩니다.
5원까지 전부 계산하면, 모든 값이 1이 됩니다.

 

2원 짜리 화폐 계산.

인덱스012345

dp

1

1

1+1=2

1+1=2

1+2=3

1+2=3

1원은 계산할 수 없습니다. 점화식이 사용될 수 있는 조건은 현재 금액이 화폐단위 이상이어야 가능합니다. 그 이외에는 계산하면 에러나고, 계산 할 필요조차 없습니다.
2원은 2원 짜리 1개로 가능합니다. 정확한 값을 지불하여 0번인덱스 참조 되어 1(기존값) + 1(0번인덱스참조값) = 2가 갱신됩니다.
3원은 2원 짜리 1개 내고, 나머지 1원 입니다. 1원을 만들 수 있는 경우의 수를 더합니다. 1(기존값) + 1(1원을 만드는 경우의 수) = 2가 갱신됩니다.
4원은 2원 짜리 1개 내고, 나머지 2원 입니다. 2원을 만들 수 있는 경우의 수는 새로 갱신 된 값을 그대로 참조합니다. 1(기존값) + 2(2원을 만드는 경우) = 3이 갱신됩니다.
5원은 2원 짜리 1개 내고, 나머지 3원 입니다. 3원을 만들 수 있는 경우의 수도 새로 갱신 한 거 사용하도록 합니다. 1(기존값) + 2(3원을 만드는 경우) = 3이 갱신됩니다.

 

5원 짜리 화폐 계산.

인덱스012345

dp

1

1

2

2

3

3+1 = 4

마지막으로 5원 짜리의 화폐를 계산합니다.
현재 금액은 반드시 단위 화폐 이상일 경우만 계산이 가능하다고 했으므로,
5원을 지불하는 경우만 계산이 됩니다. 당연히 정확히 지불이 되므로, 0번 인덱스를 참조합니다.
1값을 가져오고, 기존 값인 3을 더해 총 4가지의 경우의 수 있다는 것을 알 수 있습니다.

 

 

이렇게 momney 의 for문을 돌면서 만들 수 있는 수를 센다!

 

 

모범답안

def solution(n, money):
    answer = 0
    dp = [0 for i in range(n+1)]
    dp[0] = 1
    # dp[현재해당가격] += dp[현재해당가격 - 현재화폐의액수] 라는 점화식
    for m in money:
        for i in range(len(dp)):
            if m <= i:
                dp[i] += dp[i - m]
    
    return dp[-1]

풀이 출처:

https://school.programmers.co.kr/questions/25161

프로그래머스

 

---

※ 알아야 할 것

- dp... 0번째 인덱스 자리를 주자..!!