[백준] 14916 거스름돈

문제

• 2원, 5원짜리를 사용해 N원을 만들 때, 최소 동전의 개수 리턴하기
• N원을 만들 수 없다면 -1 리턴하기
• 1 <= N <= 100,000

 

풀이

• 5원을 최대한 사용한 뒤, 2원으로 해당 금액을 만들 수 있는지 확인하기.
• 5원을 최대한 사용했을 때 남은 금액이 홀수면 5원 대신 2원을 3개 더 사용해서 금액을 만들 수 있다.
• 1원과 3원은 만들 수 없는 금액이므로 예외처리 해준다! 

 

N = int(input())

if N == 1 or N == 3 :
    print(-1)
else :
    five = N // 5
    two = (N % 5) // 2
    
    print(five + two) if (N % 5) % 2 == 0 else print(five-1 +two+3)

 

References

• 백준 그리디