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

말하는 감자·2024년 9월 11일

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

코딩테스트 유형별 풀이

목록 보기

23/67

1. 오늘의 학습 키워드

그리디 알고리즘

2. 문제: 거스름돈 (5585번)

단계: 🥉브론즈 2단계
유형: 그리디 알고리즘
출처: https://www.acmicpc.net/problem/5585

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	47321	31082	26484	65.628%

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

출처

!https://licensebuttons.net/l/by-sa/4.0/88x31.png

Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2007/2008 예선 1번

문제를 번역한 사람: baekjoon, sbjwin
문제의 오타를 찾은 사람: roeniss, sgchoi5

알고리즘 분류

그리디 알고리즘

3. 나의 풀이

문제 풀이 및 접근

이 문제는 손님이 물건을 사고 1000엔 지폐를 냈을 때, 거스름돈에 포함된 잔돈의 개수를 최소로 하는 방법을 구하는 문제입니다. 사용할 수 있는 동전은 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이며, 동전은 무한정으로 있다고 가정합니다.

최소의 동전 개수로 거스름돈을 줄 수 있는 방법은 가장 큰 단위의 동전부터 최대한 사용하는 것입니다. 이는 그리디 알고리즘의 전형적인 예제로, 매 순간 최적의 선택을 함으로써 전체 최적해를 구할 수 있습니다.

접근 방법

거스름돈 계산: 먼저, 지불해야 할 금액을 1000엔에서 빼서 거스름돈을 계산합니다.
동전 단위 리스트: 사용할 수 있는 동전 단위를 큰 값부터 배열로 정의합니다.
큰 단위 동전부터 거슬러 줌: 거스름돈을 큰 단위의 동전부터 나누어 몫은 동전의 개수로 누적하고, 나머지는 다음 작은 단위의 동전으로 처리합니다.
총 동전 개수 계산: 각 동전 단위별로 필요한 동전 개수를 모두 더하여 총 동전 개수를 구합니다.

코드 설명

import sys

def solution(charge):
    cnt = 0  # 거스름돈에 사용된 동전의 총 개수

    # 사용 가능한 동전 단위 목록 (큰 단위부터)
    coins = [500, 100, 50, 10, 5, 1]

    for coin in coins:
        cnt += charge // coin      # 해당 동전으로 거슬러 줄 수 있는 최대 개수
        charge %= coin             # 해당 동전으로 거슬러 주고 남은 금액 업데이트

    return cnt  # 총 동전 개수 반환

# 입력 처리
payment = int(sys.stdin.readline().strip())  # 지불해야 할 금액 입력
change = 1000 - payment                      # 거스름돈 계산

# 결과 출력
print(solution(change))

상세 설명

동전 단위 리스트 생성:
```
coins = [500, 100, 50, 10, 5, 1]
```
사용할 수 있는 동전 단위를 큰 값부터 리스트에 저장합니다.
동전 개수 계산:
```
for coin in coins:
    cnt += charge // coin
    charge %= coin
```
- charge // coin은 현재 동전 단위로 거슬러 줄 수 있는 최대 개수를 계산합니다.
- charge %= coin은 해당 동전으로 거슬러 주고 남은 금액을 계산합니다.
- 이 과정을 모든 동전 단위에 대해 반복하여 총 동전 개수를 구합니다.
거스름돈 계산:
```
payment = int(sys.stdin.readline().strip())
change = 1000 - payment
```
손님이 지불해야 할 금액을 입력받고, 1000엔에서 빼서 거스름돈을 계산합니다.
결과 출력:
```
print(solution(change))
```
계산된 총 동전 개수를 출력합니다.

시간 복잡도

이 알고리즘은 동전 단위의 개수(6개)에 따라 일정한 반복을 수행하므로, 시간 복잡도는 $O(1)$ 입니다.
동전 단위의 종류는 고정되어 있으므로 입력 금액의 크기에 관계없이 항상 일정한 시간이 소요됩니다.

예시

예제 입력 1

예제 출력 1

설명:

거스름돈은 1000 - 380 = 620엔입니다.
동전으로 거슬러 주는 방법:
- 500엔 동전 1개 사용 → 남은 금액: 120엔
- 100엔 동전 1개 사용 → 남은 금액: 20엔
- 10엔 동전 2개 사용 → 남은 금액: 0엔
총 동전 개수는 4개입니다.

예제 입력 2

예제 출력 2

설명:

거스름돈은 1000 - 1 = 999엔입니다.
동전으로 거슬러 주는 방법:
- 500엔 동전 1개 사용 → 남은 금액: 499엔
- 100엔 동전 4개 사용 → 남은 금액: 99엔
- 50엔 동전 1개 사용 → 남은 금액: 49엔
- 10엔 동전 4개 사용 → 남은 금액: 9엔
- 5엔 동전 1개 사용 → 남은 금액: 4엔
- 1엔 동전 4개 사용 → 남은 금액: 0엔
총 동전 개수는 15개입니다.

마무리

이번 문제는 그리디 알고리즘의 기본 원리를 잘 보여주는 예제였습니다. 매 순간 가장 큰 단위의 동전을 선택하여 거스름돈을 최소 개수의 동전으로 줄 수 있었습니다. 실제 코딩 테스트에서도 자주 등장하는 유형이므로 익숙해지는 것이 중요합니다.

이번 문제를 통해 그리디 알고리즘의 개념을 다시 한 번 복습하고, 효율적인 문제 해결 방법을 연습할 수 있었습니다.

말하는 감자

할 수 있다

이전 포스트

[그리디] 코딩테스트 문제 TIL (보물) - 백준 1026번

다음 포스트