[Programmers]Python_거스름돈

문제

문제 설명

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 해주세요.

코드

def solution(n, money):
    pack = []
    money.sort() #오름차순 정렬
    for i in range(len(money) + 1): #0부터 돈의 개수를 차례대로 순회
        pack.append([]) #현재 돈의 개수를 기준으로 경우의 수를 추가할 리스트를 생성
        for j in range(n + 1): #현재 돈의 개수로 만들 수 있는 금액을 0부터 n까지 순회
            #돈의 개수가 0개 또는 금액이 0일때 하나의 경우 즉, 금액이 딱 떨어진 것과 같은거라고 본다
            if i == 0 or j == 0:
                pack[i].append(1)
            #돈의 개수가 1개일때는 각 금액을 순회하며 해당 금액을 만들 수 있는지 없는지에 따라서 0, 1을 추가한다
            #가장 적은 금액인 첫 번째 돈으로~
            elif i == 1:
                if j >= money[0] and j % money[0] == 0:
                    pack[i].append(1)
                else:
                    pack[i].append(0)
                    
            #돈의 개수가 2개일때는 1개일때 썼던 돈 다음으로 금액이 큰 돈을 더 사용해야한다
            #그리고 그 돈이 현재 금액보다 크다면 해당 금액을 만들 수 없으므로 전에 1개일때 썼던 돈밖에 못쓴다
            #하지만 현재 금액보다 작거나 같다면 전에 1개일때 썼던 돈이 만들 수 있는 경우의 수와 만들어야하는 금액
            #에서 2번째 돈의 금액을 뺀 금액을 2번째 돈으로 만들 수 있는 경우의 수의 합이 현재 금액을 만들 수 있는 경우의 수 이다.
            #이후에 진행과정에서 좀 더 이 부분을 설명해보겠다.
            elif money[i - 1] <= j:
                pack[i].append((pack[i - 1][j] + pack[i][j - money[i - 1]]) % 1000000007)
            else:
                pack[i].append(pack[i - 1][j])

    return pack[-1][-1]

 

진행 과정

예제 #1

n = 5

money = [1,2,5]

 

우선 금액이 0일 때와 화폐의 개수가 0일 떄를 제외하고 그 이후부터 한 번 짚어보자.

 

1개일 때

화폐 1개로 만들 수 있는 거스름돈을 한 번 판단해보자. 단, 1개로 만들때는 가장 적은 금액의 화폐만을 사용한다. 그 이유는 화폐 2개 이후부터 다른 화폐들도 사용하면서 알 수 있다.

 

현재 예제에서 가장 적은 금액의 화폐인 1로 만들 수 있는 금액들을 위 그림과 같이 보면 다행히도 1, 2, 3, 4, 5 모두 만들 수있다. 물론 하나의 화폐를 사용하였기때문에 경우의 수는 1이 된다. 만약 해당 금액을 만들 수 없다면 당연히 0이 되겠다.

 

2개일 떄

다음은 화폐의 개수가 2개일 때이다. 여기서부터가 중요한데... 일단 거스름돈 1을 만들어야할 때를 생각해보자.

 

바로 위에 줄을 보니 가장 적은 화폐인 1로 거스름돈 1을 만들 수 있는 경우가 1이 있다. 그리고 화폐 1과 다음으로 금액이 큰 화폐 2로는 거스름돈 1을 안타깝게도 만들 수가 없다. 그렇다면 화폐를 2개 사용하더라도 거스름돈 1을 만들 수 있는 경우는 하나밖에 없다는 것이 된다.

 

거스름돈이 2일때... 화폐 1로는 당연히 하나의 경우로 만들 수 있다는 것을 이제 알 수 있다. 그리고 화폐 1과 다음으로 금액이 큰 화폐 2로도 거스름돈 2를 만들 수 있다. 이 또한 화폐 1은 내지않고 화폐 2 자기 자신 하나만 내면 되므로 경우가 하나 밖에 없다. 그러하다면 거스름돈이 2일때는 경우가 2가지 있다는 것이다.

 

좀 더 진행해보자.

2개일 때

거스름돈 3일때는 이제 가뿐하게 계산할 수 있을 것이다. 화폐 1로 만들 수 있는 경우 하나와 화폐 1과 화폐 2로 만들 수 있는 경우 각각 1개씩 냄으로서 경우가 하나있으므로 총 경우가 2개 생긴다.

 

자, 이제 이쯤부터 화폐 1과 화폐 2로 만들 수 있는 경우를 어디에서 가져올지 생각해보자. 거스름돈 3일때 화폐 2를 빼면 화폐 1이 남는다. 이 말은 화폐 2가 거스름돈 2를 낼 수 있는 것은 자기 자신 하나를 내는 경우밖에 없으니 화폐 1을 낼 수 있는 경우만 보면 된다는 것이다. 쉽게말하면 화폐 1과 화폐 2로 거스름돈 3을 만들어야하는 데 화폐 2로는 2개 이상 못내니까 남은 거스름돈 1은 전에 화폐 1과 화폐 2로 만들 수 있는 경우를 가져오자는 것이다. 설명이 다소 부족하지만 계속 진행하면서 감을 잡아보자.

 

그렇다면 전에 거스름돈 2일때는 어떻게 해야할까? 화폐 2를 내버리면 거스름돈이 0이 되버린다. 그러면 전에 화폐 1과 화폐 2로 거스름돈 0을 만들 수 있는 경우를 가져와야하는데 아직 아무것도 없다.

 

거스름돈 0일 떄

 

상식적으로 화폐 1과 화폐 2로 거스름돈 0을 만들 수 있는 경우는 하나도 없다. 하지만 여기서는 무조건 하나는 있는 것으로 표현해준다. 그러면 화폐 1을 하나도 내지않고 화폐 2로만 거스름돈을 낼 수 있는 경우가 된다.

 

이해를 좀 더 돕기위해 나머지 거스름돈 4, 5를 만들 수 있는 경우만 더 진행해보고 전체적인 모양을 보자.

 

거스름돈 4일때 화폐 1로 만들 수 있었던 경우 하나와 화폐 1과 화폐 2로 만들 수 있는 경우는 화폐 2를 뺀 거스름돈 2를 만들 수 있는 경우를 전에 알아보았던 2가지의 경우를 더해준다. 그러면 총 3가지의 경우가 있는 것이다.

 

거스름돈 5일때 화폐 1로 만들 수 있었던 경우 하나와 화폐 1과 화폐 2로 만들 수 있는 경우는 화폐 2를 뺀 거스름돈 3을 만들 수 있는 경우를 전에 알아보았던 2가지의 경우를 더해준다. 그러면 총 3가지의 경우가 있는 것이다.

 

결과

계속 진행하면 위 그림과 같은 모양이 된다.

 

코드의 진행은 다음과 같다.

 

1) pack = [[1, 1, 1, 1, 1, 1]]

2) pack = [[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]

3) pack = [[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 2, 2, 3, 3]]

4) pack = [[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 2, 2, 3, 3], [1, 1, 2, 2, 3, 4]]