[백준 / python] 5585번 거스름돈 B2

오늘은 그리디 알고리즘 유형인 백준 5585번 문제, 거스름돈를 풀어보겠습니다!

 

< 문제 확인 >

https://www.acmicpc.net/problem/5585

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

타로가 1000엔 지폐를 사용하여 물건을 구매했을 때, 잔돈을 계산하는 문제입니다.

잔돈으로 사용할 수 있는 동전은 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 있으며,

잔돈을 줄 때 가능한 최소 개수의 동전을 사용해야 합니다.

 

✅ 그리디 알고리즘( Greedy Algorithm )이란?

현재 상황에서 지금 당장 좋은 것만 고르는 방법으로, 매 순간 가장 좋아 보이는 것을 선택합니다.

이 때, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

 

문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시하면
그리디 알고리즘을 떠올려 봅시다!

 

잔돈을 줄 때 가장 큰 단위의 동전부터 사용하여 잔돈을 주면 가장 적게 사용할 수 있습니다.

물건의 가격이 주어지면, 1000엔에서 물건의 가격을 뺀 값이 잔돈이 됩니다.

이 잔돈을 500엔, 100엔, 50엔, 10엔, 5엔, 1엔 순서로 나눠 잔돈 개수를 계산해 봅시다!

 

✔️ 가능한 시간복잡도

각 동전에 대해 잔돈을 나누는 연산을 수행하는데

주어진 동전의 종류는 고정된 6가지이므로, 시간 복잡도는 O(1)입니다.

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 입력받은 가격을 통해 잔돈을 계산합니다.

2. 잔돈을 각각의 동전으로 줄 수 있는 최대 개수를 계산하며, 남은 잔돈을 줄여나갑니다.

3. 계산된 잔돈의 개수를 출력합니다.

 

---

📌 시도 회차 수정 사항 (Optional)

무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

---

📌 정답 코드

# 구매한 물건 가격 입력
price = int(input())

# 잔돈 계산
change = 1000 - price

# 거스름돈 동전 종류 리스트
coins = [500, 100, 50, 10, 5, 1]

# 동전 개수 카운트
coin_count = 0

for coin in coins:
    if (change >= coin):
        coin_count += change // coin  # 해당 동전으로 계산 가능한 개수 추가
        change %= coin  # 나머지 잔돈 업데이트

print(coin_count)

오늘은 그리디 알고리즘을 사용한 대표유형을 풀어보았습니다!

앞으로 더 어려운 문제도 해결해 보고 싶어요 ㅎㅎ

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no