[백준 BOJ / Python ] 14916번: 거스름돈

문제 링크: www.acmicpc.net/problem/14916

14916번: 거스름돈

 

 

문제 설명

만약 n이 1이나 3이 주어진다면, 2원과 5원으로는 거슬러 줄 수 없으므로 -1을 반환합니다. 

나머지는 최소 개수의 동전으로 거슬러줘야 하므로 5원을 먼저 거슬러주는 방법을 선택했습니다. 

n을 5로 나눴을 때 나머지는 다음과 같이 5가지입니다. (x: n을 5로 나눈 몫)

• 나머지가 0일 경우
  5원으로만 거슬러 줄 수 있으므로 answer = x
• 나머지가 1일 경우
  5원을 하나 빼고 2원 3개를 추가해야 합니다.  =>  5x + 1 = 5(x - 1) + (2 * 3)
  따라서 anwer = (x - 1) + 3 = x + 2
• 나머지가 2일 경우
  2원을 하나 추가해서 거슬러 줄 수 있으므로 answer = x + 1
• 나머지가 3일 경우
  5원을 한 빼고 2원을 4개 추가해야 합니다.  =>  5x + 3 = 5(x - 1) + (2 * 4)
  따라서 answer = (x - 1) + 4 = x + 3
• 나머지가 4일 경우
  2원 두 개를 추가해서 거슬러 줄 수 있으므로 answer = x + 2

 

 

 

소스코드

n = int(input())
if n == 1 or n == 3:  # 거슬러 줄 수 없음
    answer = -1
else:
    answer = n // 5
    n %= 5
    if n == 1 or n == 4:
        answer += 2
    elif n == 2:
        answer += 1
    elif n == 3:
        answer += 3

print(answer)