동전 거스름돈 문제

이동욱

2021/08/25

Categories: 알고리즘

문제 - 거스름돈

거스름돈으로 사용할 돈이 500, 100, 50, 10 원짜리 동전이 무수히 많이 존재한다고 가정을 했을 때 거슬러 주어야할 최소한의 개수를 구하라. 단, 거슬러 주어야 할 돈은 항상 10의 배수이다.

제한 사항

아이디어

(그리디)

  1. 가장 큰 동전부터 비교를 해서 만약 동전의 크기보다 크다면 작을 때까지 뺀 후 횟수를 더한다.
  2. 그 다음 크기의 동전을 비교한다.

(그리디 - 개선된 버전)

  1. 가장 큰 동전으로 거스름돈을 나누고 몫만큼을 곱한 값을 뺀다.

코드

def solution(exchange: int) -> int:
  cnt = 0
  coins = [500, 100, 50, 10]

  for coin in coins:
    while exchange >= coin:
      exchange -= coin
      cnt += 1
    else:
      continue
  return cnt

def solution2(exchange: int) -> int:
  cnt = 0
  coins = [500, 100, 50, 10]

  for coin in coins:
      cnt += exchange // coin
      exchange = exchange % coin
  return cnt

if __name__ == "__main__":
  n = int(input())
  print(solution2(n)

참고 문헌

>> Home