[백준/그리디 알고리즘] 거스름돈

문제

 

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

 

입력

 

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

 

출력

 

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

예제 입력 1

13

 

예제 출력 1

5

 

문제 해설

 

이 문제에서 "2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다." 라는 문구를 보고 그리디 알고리즘 이라고 생각했다.

 

이 문제에서 5이상의 숫자는 모두 거슬러 줄수 있다.  홀수라면 5를 나누었을때 짝수가 되고, 짝수라면 당연히 2원으로 거슬러줄수 있기 떄문이다.

 

즉 5원보다 적고, 2의 배수가 아닌 경우에만 -1을 출력해주면 된다.

 

ex) 8원 -> (5로 나누었을때) 몫 1 , 나머지 3 

      3은 2로 나누었을때 나머지가 0이 아니므로, 5원이 거스름돈에 포함되지 못한다는 것을 알수 있다.

      따라서 이러한 경우에는 5원의 개수를 1개 빼주고, 입력받은 5값을 나눈 나머지에 5를 하나 더한 뒤  그것을 2로 나눈 몫을 구하면 된다.

 

ex) 13원 -> (5로 나누었을때) 몫2, 나머지 3

       마찬가지로 3원을 2로 나눌수가 없다. 그래서 5원의 개수를 한개 줄이고, 나머지에 추가하여 2로 나눈다.

       5원의 개수 2-1 = 1, 13을 5로 나눈 나머지 3+5 = 8로 바꾼 뒤 2로 나눈다.

       5원의 개수 1개, 2원의 개수 4개가 13원을 거스르는 최소 개수의 동전임을 알 수 있다.

 

n = int(input())
if n in [1,3]: # 5원보다 적고, 2의 배수가 아닌 경우에만 -1을 출력
    result -1
elif (n%5)%2 == 0: 
    result = (n//5) + (n%5)//2
else:
    result = ((n//5)-1) + ((n%5+5)//2) # 8, 13 같이 나머지가 나누어 떨어지지 않는 경우
print(result)