[브론즈2]백준 5585번(거스름돈) - 코테공부 27일차(2025.02.18)

문제유형

그리디 알고리즘

풀이 방법 도출 과정

1. 가장 최적의 해 = 가장 빠른 순서대로 이기에 적합한 문제이다.

2. 이러한 것은 그리디 알고리즘을 사용하면 적합하다. 

3. 우선 순위는 가장 많은 동전이여야한다는 점을 기억하며 코드를 작성해보도록 하겠다. 

시간 복잡도

시간 복잡도는 O(1)이다. 그리디 알고리즘을 사용했기 때문이다. 

코드 및 간단설명

그리디 알고리즘을 사용하여 간단하게 풀었다. 

N = int(input())
N = 1000 - N
count = 0

for coin in [500, 100, 50, 10, 5, 1]:
    count += N // coin
    N %= coin

print(count)

다른 풀이

1) math함수 사용

divmod를 사용하여 몫과 나머지를 같이 계산하는 방법으로 더 효율적으로 풀수도 있다. 

N = 1000 - int(input())  # 거슬러 줄 금액
count = 0
coins = [500, 100, 50, 10, 5, 1]

for coin in coins:
    q, N = divmod(N, coin)  # 몫과 나머지를 한 번에 계산
    count += q

print(count)