백준 문제 풀이 - 거스름돈 14916번

📜 문제 이해하기

춘향이는 편의점 카운터에서 일한다.
손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.
예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

💡 문제 재정의

거스름돈이 주어졌을 때 5원과 2원으로 가장 적은 동전으로 줄 때 이 동전의 개수를 출력하자.

✏️ 계획 수립

그리디 알고리즘을 사용하면 가장 적은 동전을 고를 수 있다. 먼저 5원을 제일 많이 쓰는게 가장 동전을 적게 쓰기 때문에 5원을 뺄 수 있는지 먼저 고민한다. 이 때 아래 두가지를 고민한다.
1. 현재 거스름돈이 5원보다 커야한다.
2. 현재 거스름돈에서 5원을 뺀 금액이 5로 나눠지거나 2로 나눠줘야 한다.
위 과정이 만족되면 5원을 빼고 다시 남은 금액으로 비교한다. 만약 5원을 뺄 수 없다면 2원을 위와 같은 과정으로 다시 비교하고 2원조차 뺄 수 없다면 -1을 출력한다.

💻 계획 수행

if __name__ == '__main__':
    n = int(input())
    cnt = 0
    while n > 0:
        if n >= 5 and ((n - 5) % 5 == 0 or (n - 5) % 2 == 0):
            n -= 5
            cnt += 1
        elif n >= 2 and ((n - 2) % 5 == 0 or (n - 2) % 2 == 0):
            n -= 2
            cnt += 1
        else:
            cnt = 0
            break
    if cnt:
        print(cnt)
    else:
        print(-1)

🤔 회고

그리디 알고리즘으로 풀 수 있는 문제였다. 그리디 알고리즘은 지금 당장 취할 수 있는 가장 좋은 것을 취하는 알고리즘이기에 위와 같은 문제를 풀기에 적합하다.