[이코테 # Greedy1] 거스름돈 문제 풀이

* Greedy Algorism

" 현재 상황에서 지금 당장 좋은 것만 고르는 방법"

 

* 거스름돈 문제

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수.(단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.)

# 해설 보기 전 original 본인 답변

# 500원= Five_H, 100원= One_H, 50원 = Fifty , 10원 = Ten
# 손님에게 거슬러줘야 할 돈 N = change
# 상품 가격 : ProductPrice = 1350원
ProductPrice = 740
print("상품 가격 : %d" % ProductPrice)
payment = int(input("받은 돈: "))	# 2000원을 받는다.
change = payment - ProductPrice
Five_H = change // 500
One_H = (change - 500 * Five_H) // 100
Fifty = (change - 500 * Five_H - 100 * One_H) // 50
Ten = (change - 500 * Five_H - 100 * One_H - 50 * Fifty) // 10
total_coin = Five_H + One_H + Fifty + Ten

# 거스름돈 계산
if change < 0:
    print("현금이 부족합니다.")
else:
    print("거스름돈은 %d 원입니다." % change)
    print("500원 : %d, 100원 : %d, 50원 : %d, 10원 : %d" % (Five_H, One_H, Fifty, Ten))
    print("거슬러줘야 할 동전의 최소 개수는 %d개 입니다." % total_coin)

 

* 거스름돈 문제 해설 답

현 거스름돈 문제에서는 큰 단위가 항상 작은 단위의 배수 형태이므로 최적의 해를 보장할 수 있다.

N = 1260
count = 0

coin_type = [500, 100, 50, 10]

for i in coin_type:
    count += N // i
    N = N % i
print(count)