거스름돈

2yunseong·2022년 2월 9일
0

문제

당신은 음식점의 계산을 도와주는 직원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 있다 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

비슷한 문제

백준 5585번 : 거스름돈

아이디어

내가 거슬러 줄 수 있는 가장 높은 금액의 거스름돈부터 거슬러줄수 없을 때까지 거슬러준다.

내 풀이

거스름돈을 다 거슬러 줄 때 까지 (money == 0) 반복문을 돌린다. 반복문 안에는 생각한 아이디어를 바탕으로 조건문을 구성하여 준다.
조건문 이후에 다른 조건문을 실행시키지 않도록, continue 문을 통해 탈출한다. (혹은 elif 를 사용)

money = int(input())
coinCount = 0

while money != 0:
    if money >= 500:
        coinCount = coinCount + 1
        money = money - 500
        continue
    if money >= 100:
        coinCount = coinCount + 1
        money = money - 100
        continue
    if money >= 50:
        coinCount = coinCount + 1
        money = money - 50
        continue
    if money >= 10:
        coinCount = coinCount + 1
        money = money - 10

print(coinCount)

피드백

책을 보니 더 좋은 방법이 존재했다. 내 해결 과정보다 더 내가 생각한 아이디어에 맞는 로직의 코드였다. 어떤 점에서 그랬는지 살펴보자.

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin
    n %= coin

count += n // coin 에서, 지금 거스름돈 단위로 거슬러 줄수 있는 동전을 모두 카운트 한다. 내가 생각한 방법은
"1260원은 500원보다 크니까 하나 거슬러 주고.. 이제 760원 남았으니까 다시 500원..."
이라면 책은
"1260원이니 일단 500원 짜리 2개 거슬러 줄 수 있겠고, 그 다음 260원 남으니까 100원짜리도 2개 ..."
이 되므로 말로 풀어 설명해보아도 훨씬 좋은 방법임을 알 수 있다.

기타

  • 파이썬은 단항 연산자(++ , --)가 없다. 주의하자.
  • 그리디 알고리즘으로 문제의 해법을 찾알을 때는 그 해법의 정당성을 검토해보아야 한다.
  • 소요시간 : 7분
profile
개발 발자국 남기기

0개의 댓글