Algorithm-problem-solving

Baekjoon Online Judge 5585번 거스름돈 문제

백준 저지 5585번 거스름돈 문제 Pseudo code + Python code

1
2
3
4
5
6
7
8
9
10
11
product_price = int(input())
coin_unit = [1, 5, 10, 50, 100, 500]
coin_unit.sort(reverse=True)
changes = 1000 - product_price
coin_count = 0
for unit in coin_unit:
  if changes >= unit:
    num_of_coin = changes // unit
    changes -= unit * num_of_coin
    coin_count += num_of_coin
print(coin_count)

이 문제는 대표적인 그리디 알고리즘 문제 유형으로, 최소한의 동전 갯수를 사용해서 거스름돈을 만드는 문제이다.
사용될 동전의 종류를 저장하고 있는 리스트를 역정렬한 뒤에, 해당 리스트를 순회하면서 사용될 동전의 갯수를 카운트하면 되는 간단한 문제이다.