[programmers/py] 거스름돈

거스름돈

https://school.programmers.co.kr/learn/courses/30/lessons/12907

문제 설명

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

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

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

풀이

보면 DFS를 이용해 완전 탐색문제로 접근했는데 아무리봐도 DFS는 답이 아닌 것 같아서 dp로 접근했습니다.

dp를 n+1개를 생성합니다.
각 dp의 index는 가격을 의미합니다.

dp[0] 즉, 0원 인 경우 1로 변경해
dp = [1, 0, 0, 0, 0, 0]으로 값을 초기화합니다.

위 예시를 보면 [1,2,4]원을 이용해 5원을 만들 수 있습니다.
1, 2, 4원의 경우 각각 dp[i]부터 시작합니다. 2원이면 2부터 5까지

식을 보면 우선 money에서 1인 경우 dp[1]부터 dp[5]까지의 값을 갱신합니다.
값은 dp[i] += dp[i - 1(money)]로 갱신해줍니다.

def solution(n, money):
    dp = [0] * (n+1)
    dp[0] = 1
    
    for m in money:
        for i in range(m, n+1):
            dp[i] += dp[i-m]   
    return dp[-1]