[그리디] 코딩테스트 문제 TIL (거스름돈) - 백준 14916번

말하는 감자·2024년 12월 26일

TIL algorithm baekjoon greedy python 그리디 백준 알고리즘 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

50/67

오늘 문제는 백준 2839문제와 비슷한 문제입니다. 그럼 살펴보겠습니다.

1. 오늘의 학습 키워드

그리디 알고리즘

2. 문제: 14916. 거스름돈

단계: 🥈 실버 5단계
주제:
출처: https://www.acmicpc.net/problem/14916

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

3. 문제 풀이

Step1. 문제 이해하기

거스름돈 n원이 주어졌을 때, 동전의 개수가 최소가 되도록 거슬러 주는 문제입니다.

동전은 2원과 5원짜리가 무한정 있다고 합니다.

주어진 문제는 그리디 알고리즘하면 생각나는 거스름돈 문제와 약간 다릅니다.

저희가 흔히 아는 거스름돈 문제는 주어진 동전이 가장 큰 동전과 나머지 동전들이 배수 관계를 가지기 때문에 큰 동전부터 거슬러 주면 됩니다. 하지만 이 문제는 그렇지 않기 때문에 다르게 생각해야 합니다. (거의 같긴 하지만,,,)

우선, 입출력을 살펴보도록 하겠습니다.

Input:
- 첫째 줄에 거스름돈 액수 n이 주어집니다. n은 1이상 $10^5$ 이하 입니다.
Output:
- 거스름돈 동전의 최소 개수를 출력합니다. 만약 거슬러 줄 수 없으면 -1을 출력합니다.

Step2. 문제 분석하기

주어진 문제에서 동전들은 서로 배수 관계가 아닙니다. 그러면 어떻게 이 동전들의 조합으로 최소 개수를 만들수 있을까요?

동전은 2원과 5원이 있습니다.

5의 배수로 나눠지기전까지 2로 빼다가 5로 나눠지게 되면 나눠주면 해결할 수 있습니다.

예시 중 13원이 있습니다. 이 돈을 5원짜리로 먼저 접근하려고 하면 5*2 = 10, 13 - 10 = 3원이 되고 이것은 2원으로 할 수가 없게 됩니다.

하지만 13원 - (2원 * 4) = 5원이 되므로 최종적으로 2원 4개, 5원 1개로 5개를 구할수 있습니다.

즉, 해당 문제는 현재 거스름돈에서 줄 수 있는 최선의 상황을 수행하는것이 최종적인 정받을 도출하는 그리디 알고리즘 유형의 문제인 것입니다.

Step3. 코드 설계

n이 0이하일떄까지 반복문을 돌립니다.
n이 5로 나누어떨어진다면 바로 결과를 반환합니다.
그렇지 않으면 2를 빼면서 5로 나누어떨어질때까지 카운트를 측정합니다.

Step4. 코드 구현

import sys
n = int(sys.stdin.readline().strip())
def sol(n):
    cnt = 0
    while n >= 0:
        if n % 5 == 0:
            cnt += n // 5
            return cnt
        else:
            n -= 2
            cnt += 1
    return -1
print(sol(n=n))

코드 설명:
1. 입력 처리:
  - n은 거스름돈으로 주어진 금액입니다. 입력값은 정수형으로 변환합니다.
2. 그리디 알고리즘:
  - cnt는 동전 개수를 세는 변수로 초기값은 0입니다.
  - 반복문을 통해 n이 0 이상일 동안 다음을 반복합니다:
    1. n이 5로 나누어떨어지면 (n % 5 == 0), 해당 몫(n // 5)을 동전 개수에 추가하고 결과를 반환합니다.
    2. 그렇지 않으면, 2를 빼고 동전 개수를 1 증가시킵니다.
  - 반복문이 종료되지 않은 상태에서 n이 음수가 되면, 주어진 동전으로 정확히 거슬러 줄 수 없으므로 1을 반환합니다.
3. 출력 결과:
  - 함수 sol(n)의 반환값을 출력합니다.
시간 복잡도: $O(n)$
결과: