프로그래머스 - 거스름돈 [Python]

 문제

 

 

 문제 상황

 

- 동전의 종류가 결정되어 있지 않은 상태에서 입력받은 동전의 종류를 통해 거스름돈을 줄 수 있는 방법의 수를 계산한다.

 

 

 

 해결 전략

 

- 탐욕적 방법으로 계산했던 10원, 50원, 100원.. 의 문제와 다르게 이 문제는 하나의 거스름돈을 만드는데 훨씬 많은 경우의 수가 생긴다. 그래서 DP를 사용해야 한다. 

 

 

 

 코드

 

# n 원, money는 거스름돈의 종류를 담은 list
def solution(n, money):
    # cache[x][y] 는 동전 1~x로 y원을 만들기
    cache = [[0 for i in range(n+1)] for j in range(len(money))]
    # 0,0을 초기화
    cache[0][0] = 1
    # 최소의 크기 동전으로 금액을 만들 수 없는 경우가 존재
    # money[0]의 배수만 거스름돈으로 만들수 있으므로 갱신
    for i in range(money[0],n+1,money[0]):
        cache[0][i] = 1
    # money[1]부터 추가로 사용하며 cache 채우기
    for i in range(1, len(money)):
        # 0원부터 n원까지 만들어가기
        for j in range(n+1):
            # money[i]를 이용해 j원을 만들 방법이 없다.
            if j < money[i]:
                cache[i][j] = cache[i-1][j]
            # 방법이 존재하면
            else:
                # 동전 money[i]를 사용하지 않은 방법의 가지수 + 동전 money[i]를 한개 사용한 가지수
                cache[i][j] = (cache[i-1][j] + cache[i][j-money[i]])%1000000007
    return cache[len(money)-1][n]

 

 

 해설

 

- 문제를 생각했을 때 트리 노드를 탐색해가는 DFS 혹은 BackTracking으로 접근했지만 전형적인

DP문제였다.

 

- 2차원 cache를 만들어 cache[x][y]가 의미하는 것은 money[0]부터 money[x]까지 동전을 이용해 y원을 만드는 방법의 수이다.

 

- cache[x][y]는 동전 money[x]가 y원보다 클 경우 money[x]를 사용할 방법이 없어 cache[x-1][y], 즉 동전 money[x]를 사용하지 않고 y원을 만드는 방법의 수가 된다.  money[x]원이 y원보다 작을 경우 money[x]를 사용하고 x까지의 동전을 사용해 y-money[x]원을 만드는 방법의 수의 합이 된다.  

 

- 전체를 순회하며 cache를 채워나가고 cache[len(money)][n]이 답이 된다.

 

 

 

 

 새로 학습한 것 & 실수 

 

- dp라는 것을 생각하지 못했다. 막연하게 피보나치와 비슷하게 결과물을 더해가는 구조라는 생각은 들었지만 dp 유형이라고 생각하지 못했다. 

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/12907