[책-알고리즘퍼즐68]5.환전자판기

문제

환전 자판기가 있다. 잔돈으로 10, 50, 100, 500 그리고 최대 갯수 15개로 설정 되어 있다. 사용자가 천원을 넣었을때 이때 환전 자판기가 거슬러 줄수 있는 가짓수를 계산하여라. (잔돈 설정, 최대갯수 설정에 확장성이 있게 짤것)

 

난이도

IQ 75

 

목표시간

15분

 

문제정답(사용언어:python)

1. deque 와 // 를 이용

from collections import deque

cnt =0
def change(target, coins, usable):
    global cnt
    coin = coins.popleft()
    if len(coins) == 0:
        if target//coin <= usable:
            cnt +=1
    else :
        for i in range(0, target // coin +1 ) :
            change(target - coin*1, coins,copy(), usable -i)

change(1000, deque([500, 100, 50, 10]) , 15)
print(cnt)

 

배운점

파이선 // 연산기호 => 나머지 연산이후 정수부분만 반환한다.

단순하게 중첩 for문을 이용하여 풀면 쉽고 간단한 문제. 하지만 문제에서는 확장성을 고려하여 재귀형태로 답을 요구한듯 하다. 절차형 언어에서는 재귀보다는 반복문을 선호하지만 함수형 언어에서는 반복문보다는 재귀를 선호 한다고 한다. 이책에 모든 풀이는 파이썬으로 작성되어 있어서 대부분의 반복문 처리할 내용들이 재귀로 풀이되어 있다. 

여지껏 재귀는 디버깅이 쉽지 않고 코드 이해도를 떨어트린다고 생각해서 기피해왔지만 알고리즘적인 문제 해결면에서는 재귀적인 표현도 괜찮은것 같다. 이참에 재귀표현에 익숙해져야 겠다.