[Alg] Greedy - 거스름돈

거스름돈

문제 상황
거스름돈은 500원, 100원, 50원, 10원짜리 동전만 사용 (무한하다고 가정)
거스름돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
단, N은 항상 10의 배수

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n//coin
    n %= coin
    
print(count)
    
    

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 떄문에 그리디 알고리즘이 정당함

만약 거스름돈 화폐 단위가 배수가 아닌, 무작위라면 그리디 알고리즘으로 불가능

대부분 그리디 알고리즘 문제에서 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

어떤 코딩테스트 문제를 만났을 때, 바로 문제 유형을 파악할 수 없다면 그리디 알고리즘을 의심
만약 그리디 알고리즘으로 해결 방법을 찾을 수 없다면 다이나믹 프로그래밍, 그래프 알고리즘 등으로 고민

먼역