파이썬 Python | 알고리즘 | 백준 거스름돈

⭕ 파이썬 Python | 알고리즘 | 백준 거스름돈

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• 그리디(Greedy) 알고리즘: 그리디 알고리즘은 매 순간 최적의 선택을 하여 전체 문제의 최적해를 찾아가는 방식이다. 이 문제에서 그리디 알고리즘을 사용하는 이유는 화폐 단위가 배수 관계로 화폐 단위가 큰 것부터 사용하여 최적의 해를 빠르게 구할 수 있기 때문이다. 큰 단위의 동전부터 차례대로 선택하지 않으면, 더 많은 동전을 사용하게 되어 비효율적인 해를 도출할 수 있다. 따라서, 동전 단위를 큰 것부터 작은 것 순서대로 리스트에 저장하고, 순차적으로 거슬러 주는 방식을 사용한다.
• 큰 단위의 동전부터 사용하면 최적의 해를 보장할 수 있는 이유는, 큰 단위의 동전이 작은 단위의 동전으로 구성될 수 없기 때문이다. 예를 들어, 500엔은 100엔 동전 다섯 개로 교환할 수 있지만, 그리디 알고리즘에서는 500엔 동전을 먼저 사용하기 때문에 최적해를 빠르게 찾을 수 있다.
• 시간 복잡도: 동전의 종류 K개만큼 반복을 수행하므로, 시간 복잡도는 O(K)이다. 동전의 종류가 총 6개이므로, 6번정도의 연산이 필요하고 시간초과를 고민하는 것이 의미가 없을 정도이다.

 

➡️ 코드 설계하기

• 지불할 돈(1 이상 1000 미만의 정수)을 입력받는다.
• 잔돈으로 사용할 동전 단위를 리스트에 저장한다. (500엔, 100엔, 50엔, 10엔, 5엔, 1엔)
• 가장 큰 화폐 단위부터 차례로 거슬러 준다. 남은 금액이 현재 화폐 단위보다 작아질 때까지 반복한다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회차

• 나눗셈 연산자 /를 사용하여 소수점이 출력되는 문제를 겪었다. 동전의 개수는 정수여야 하므로, 정수 나눗셈을 사용해야 정확한 값을 얻을 수 있다.

import sys

money = int(sys.stdin.readline())
charge = 1000 - money

coins = [500, 100, 50, 10, 5, 1]
count = 0

for coin in coins:
    count += charge / coin  # 소수점 문제 발생
    charge %= coin

print(count)

---

2회차

• 시간 108ms
• 정수 나눗셈 연산자 //를 사용하여 해결하였다.

import sys

money = int(sys.stdin.readline())
charge = 1000 - money

coins = [500, 100, 50, 10, 5, 1]
count = 0

for coin in coins:
    count += charge // coin  # 정수 나눗셈으로 수정
    charge %= coin

print(count)

 

➡️ 정답 코드

import sys

money = int(sys.stdin.readline())
charge = 1000 - money

coins = [500, 100, 50, 10, 5, 1]
count = 0

for coin in coins:
    count += charge // coin
    charge %= coin

print(count)