8.11 코인

문제

쿼터(25센트 ) , 다임(10센트) , 니켈 (5센트 ) , 페니(1센트)의 4가지 동전이 무한히 주어졌을때

n센트를 표현하는 모든 방법의 수를 계산하는 코드를 작성하라.

 

해결법

이 문제도 재귀로 풀 수 있으므로 부분 문제를 만드어보자 

n = 100일때 

쿼터가 0개 1개 2개 3개 4개 있을 수 있다. (4개면 100을 만들 수 있을니까!) 

그런데 1개의 쿼터로 100을 만드는 것은 0개의 쿼터로 75를 만드는 것과 같음을 알 수 있다.

이 논리를 2개의 쿼터, 3개의 쿼터에도 적용한다면 다음의 결과를 얻을 수 있다.

makeChange(100) = makeChange(0개의 쿼터로 100만들기 + makeChange(0개의 쿼터로 75만들기)

                                 + makeChange(0개의 쿼터로 50만들기 + makeChange(0개의 쿼터로 25만들기) + 1 

그 다음에는 다임, 니켈, 페니에 대해서도 같은 일을 확장해서 하면 될 것이다.

def Solution(amount, denoms):
    return getWays(amount, denoms,0)

def getWays(amount, denoms, index):
    if index >= len(denoms)-1 :
        return 1
    way = 0
    remain = amount -denoms[index]
    while remain >=0:
        way += getWays(remain, denoms, index+1)
        remain -= denoms[index]

    return way