그리디 알고리즘 예제1: 거스름돈

알고리즘 분야에서 부족함을 느껴 이전에 공부했던 책의 예제를 풀면서 복습하려고 한다.

 

사용한 책은 아래의 링크에서 확인할 수 있다. 

https://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 예스24

 

 

https://www.youtube.com/watch?v=5OYlS2QQMPA&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=12

 

---

문제 설명

 

 

나의 풀이

N = int(input())

temp = N 

N_500 = temp//500
D_500 = temp%500

temp = D_500

N_100 = temp//100
D_100 = temp%100

temp = D_100

N_50 = temp//50
D_50 = temp%50

temp = D_50

N_10 = temp//10
D_10 = temp%10

Num_coin = N_500 + N_100 + N_50 + N_10

print('거스름돈 동전의 최소 개수: {}'.format(Num_coin))

 

굉장히 단순하게 풀었다. 

 

정답을 보고 내 풀이가 허접하다는 것을 깨달았다 ㅜ

 

다음 문제는 좀 더 생각해서 풀어볼 것이다. 

 

N = int(input())
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += N//coin
    N %= coin

print('거스름돈 동전의 최소 개수: {}'.format(count))