Algorithm. 백트래킹 - 동전 거스름돈

1. 동전 거스름돈

• 총금액 800, 동전 종류 : 10, 50, 100, 400, 500
• 그리디 : 500, 100, 100, 100 -> 최적해가 아니다

소스코드

# coin[] : 동전의 금액을 젖아
# choice[] : 선택한 동전 집합
# best : 거스름돈에 대한 최소 동전 개수

def coinChange(choice, N, money):
    global best
    if best <= N:
    	return
    elif money == 0: # best > N
    	best = N
    else:
    	for i in range(len(coin):
            if money - coin[i] >= 0:
            	choice[N] = coin[i]
                coinChange(choice, N+1, money-coin[i])