코딩테스트 스터디 - 프로그래머스 거스름돈 (python)

문제

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

프로그래머스

요약

사용 가능한 동전의 종류와 지불해야할 거스름돈의 액수가 주어지면,

동전들을 활용해 액수를 맞출 수 있는 경우의수를 1,000,000,007로 나눈 수를 반환한다.

의식의 흐름

경우의 수 문제는(게다가 숫자가 커질 수 있으니 나머지를 출력하라고하면) DP를 가장 먼저 생각하게된다.

 

table[i] = i원을 만들 수 있는 경우의 수라 하면, table[0]=1이다.

 

간단하게 생각해보면, i원을 만들 수 있는 경우의 수에 x동전을 추가해 i+x원을 만들 수 있다.

즉, i원을 만드는 경우의 수 =(x원 없이 i원 만들기) + (x원 포함 i-x원 만들기) 가 되고,

x원 포함 i-x원 만들기 = i-x원을 만드는 경우의 수 = (x원 없이 i-x원 만들기) + (x원 포함 i-2x원 만들기)

이렇게 재귀적으로 표현이된다.

 

이 재귀 방식을 bottom-up 방식으로 낮은 i 부터 반복문으로 계산하면

어떤 i 시점에서 table[i-x]는 이미 x동전을 활용 해 만들 수 있는 조합을 계산 해둔게 되기 때문에,

(x원 포함 i-x원 만들기) = (i-x원 만들기)가 된다.

즉 x원부터 N원까지의 i원에 대해, table[i] += table[i-x]를 해주면 된다.

구현

자료구조

DP 테이블을 사용한다.

table[i] = i원을 만드는 경우의 수를 뜻한다.

알고리즘

동전 종류를 하나씩 늘리면서, x원부터 N원까지의 i원에 대해, table[i] += table[i-x]를 해준다.

코드

DP 테이블은 2차원밖에 안써봤는데, 이 문제는 풀다보니 1차원 배열로 완성이 됐다.

깔끔하게 식을 만드는데 시간이 오래 걸렸었다.

def solution(n, money):
    answer = 0
    table = [0 for i in range(n+1)]
    table[0] = 1
    for coin in money:
        for i in range(coin, len(table)):
            table[i] = (table[i] + table[i-coin]) % 1000000007
    return table[n]