31. Coin sums

1. 개요

문제는 이곳에서 확인할 수 있다. 1, 2, 5, 10, 20, 50, 100 그리고 200을 사용하여 200을 만드는 방법의 수를 구하는 것이 목표이다. 이 문제는 재귀함수를 사용하여 간단하게 해결할 수 있다. 즉, 200에서 100을 빼고 나면, 문제는 100을 만드는 방법의 수를 구하는 것으로 변한다. 

2. 구현: ver 1.0

재귀함수를 이용하여 구현한다. 하지만 이 방법은 그다지 효율적이진 않은데, 만약 200이 아니라 400을 구하라고 해도 생각보다 시간이 오래 걸린다. 사람들의 아이디어를 참고하여 memoization을 사용하려고 했지만 아둔하기 짝이 없어 결국 이해하지 못했다. 

# -*- coding: utf-8 -*-
import numpy as np

coins = [200, 100, 50, 20, 10, 5, 2, 1]

def find_way(remainder, coins):
    if remainder in [0, 1] or len(coins) == 1:
        return 1

    result = 0
    for idx, coin in enumerate(coins):
        if remainder - coin >= 0:
            result += find_way(remainder - coin, coins[idx:])
    return result

print(find_way(200, coins))

답은 73682이다.