[BOJ / Python] 14196 - 거스름돈

 

14916번: 거스름돈

이번에 새로 받은 이것이 취업을 위한 코딩 테스트다 with Python의 첫 예제를 풀다가 백준에서 찾아 푼 문제다.

간단한 그리디 알고리즘으로 풀 수 있다.

풀이

5 이상의 숫자는 모두 거슬러 줄 수 있다. 홀수라면 5로 나누었을 때 나머지가 짝수가 되고, 짝수라면 당연히 거슬러 줄 수 있기 때문이다.

 

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

 

문제의 조건에 맞게 최소 개수의 동전으로 거슬러 주기 위해서는 어떻게 해야 할까? 당연히 5원으로 최대한 나누고 나머지만 2원으로 나누면 된다.

 

8원을 예로 들면, 5원으로 나누었을 때 몫이 1이고 나머지가 3이다. 

 

3은 2로 나누었을 때 나머지가 0이 아니므로, 5원이 거스름돈에 포함되지 못한다는 것을 알 수 있다. 따라서 이런 경우에는 5원의 개수를 1개 빼주고, 입력받은 값을 5로 나눈 나머지에 5를 하나 더한 뒤 그것을 2로 나눈 몫을 구하면 된다.

 

13원을 예로 들어 보자. 우선 5원으로 나누게 되는데, 마찬가지로 5원 2개, 나머지 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]:
    result = -1
elif (n%5)%2==0:
    result = n//5 + (n%5)//2
else:
    result = ((n//5)-1) + ((n%5+5)//2)
print(result)