[BOJ/Python] 백준 14916번 - 거스름돈 풀이

📣코딩테스트를 위한 백준 문제 추천 모음

문제

백준 14916번 - 거스름돈

문제 정의

손님에게 거스름돈을 두 개의 동전 2원과, 5원짜리만 사용하여 돈을 줘야 하는 문제이다. 14원 같은 경우 2원짜리로 7개, 5원짜리 2개 2원짜리 2개 총 4개로 2가지 경우의 수가 존재하지만 거스름돈 동전의 최소 개수를 출력하는 문제이므로 두 번째를 출력하면 된다.

접근 방법

이 문제는 전형적인 기본 그리디 문제이다. 언뜻 보기에는 최소의 동전 개수를 출력하는 문제이므로 거스름돈을 큰 동전인 5원짜리로 먼저 나눈 후 2로 나누고 딱 나눠떨어지지 않으면 -1을 출력하면 될 거 같지만 작은 함정이 숨어있어 조심해야 한다. 항상 그리디 알고리즘으로 해결할 경우 최적의 해를 가지게 되는지 검증을 해보자.

예를 들어 춘향이가 손님에게 28원의 거스름돈을 줘야 한다고 가정해 보자. 위에서 설명한 방식대로 하면 5원짜리 동전 5개를 사용하면 남은 거스름돈이 2로 나누어떨어지지 않기 때문에 -1을 출력하지만 실제 최적의 해는 5원짜리 동전 4개 2원짜리 동전 4개로 총 8개이다.

그렇다면 이 문제를 그리디 알고리즘으로 해결하려면 항상 최적의 해를 가지고 현재 선택할 수 있는 가장 최선의 방법이 무엇인지 생각해 보아야 한다. 이 문제의 경우 5로 나누어떨어질 경우가 가장 좋은 답이 되고 답이 안된다면 답이 될 때까지 2를 빼주면 된다.

문제 해설

접근 방법에서 설명한 대로 처음 입력받은 금액을 0이 되거나 음수가 될 때까지 무한 반복문을 사용하여 5로 나누어떨어질 때까지 2를 빼면 된다. 그렇게 하면 큰 수로 나누어떨어지면 해답이 되고 안되면 작은 수인 2로 될 때까지 빼면서 진행하기에 항상 최적의 해를 가질 수 있다.

풀이

import sys
input = sys.stdin.readline

def sol(money):
    cnt = 0

    while money > 0:
        if money % 5 == 0:
            cnt += money//5
            break
        else:
            money -= 2
            cnt += 1

    if money < 0:
        print(-1)
    else:
        print(cnt)


if __name__ == '__main__':
    money = int(input())

    sol(money)

정리

이번 문제의 핵심은 최적의 해를 가지게 되는지 검증 후 그리디 알고리즘을 사용하는 기본적인 문제로 매우 쉬운 편이였다. 풀이의 시간 복잡도는 O(N)이고 시간제한이 2초와 최대 입력값이 100,000으로 여유로운 편이였기에 시간 복잡도는 생각하지 않고 문제를 풀었다.

⚡직접 문제를 풀어보고 작성한 글입니다.⚡
🙂틀린 부분이나 보완할 점이 있을 경우 언제든지 댓글 혹은 메일로 지적해 주시면 감사하겠습니다!🙂