[Python] 14916번 거스름돈

✏️ 문제

 

문제 파악

이거 설탕 배달이랑 똑같은 알고리즘이다. 보자마자 설탕 배달 생각남..

최소 개수를 출력해야 되므로 큰 단위인 5원부터 비교하지만 5원보다 크다고 무조건 5원으로 나누도록 코드를 짜지 않는 게 포인트이다. 

 

예제1의 경우 5원으로 나누게 되면 5원 2개가 나오고 나머지가 3이므로 거슬러 줄 수 없다고 나올 수 있기 때문이다. 이 점을 잘 생각하여 코드를 작성해야 한다.

 

알고리즘

• 그리디 알고리즘
• 다이나믹 프로그래밍
• 수학

 

 

코드

n = int(input())
count = 0

while n >= 0:
  if n % 5 == 0: 
  	# 5원으로 나눴을 때 나머지가 없는 경우에만 5원으로 나눔!
    count += int(n // 5)
    print(count)
    break

  n -= 2 
  count += 1
else: # 루프가 정상적(또는 조건이 거짓이 되어서)으로 종료되었을 때 실행 
	  # while 루프가 중간에 break 문에 의해 종료되지 않았을 때 실행되는 코드
  print(-1)