문제

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

손님이 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

풀이1은 나의 풀이 방법이다. 풀이2는 다른 사람의 풀이인데, 풀이2가 더 가독성이 좋고, 내가 횡설수설한 코드를 깔끔하게 정리해놓은 느낌이었다. (결국은 같은 방법인데, 나의 코드는 삥 돌아간 느낌이고 코드2는 일직선으로 쭈욱 간 느낌?)

먼저, 주어진 거스름돈을 5원으로 나눈 후, 그 나눈 횟수를 더해준다. 처음에 최대한 5원으로 나누는 것이 최소한의 동전으로 거슬러줄 수 있기 때문이다.

그 이후, 가격을 2원으로 나누어본다. 2원으로 나누어지지 않을 시, 거슬러 줄 수 없다는 것을 의미하며, 이는 바로 직전에 5원을 거슬러 준 것이 잘못되었다는 것을 뜻한다. 따라서, 거슬러준 5원을 다시 돌려받고, 나누어준 횟수를 -1 해준다.

이를 반복하면서 2원으로 나누어진다면 최소한의 개수로 거슬러줄 수 있다는 것을 의미한다.

하지만, 거스름돈이 5보다 작다면 5를 다시 거슬러주는 것이 성립되지 않으므로, 이는 따로 구분하여 2원으로 나누어서 답을 출력한다.

코드1

### 백준 14916

n = int(input())

if n >= 5:
    ans = n // 5
    n %= 5
    
    # 일단은 5원으로 전부 나누어보고, 거슬러줄 수 없다면 5원을 한 번씩
    # 돌려 받으면서 2원으로 나누는 것을 반복하여 시도
    while True: 
        if n % 2 != 0:
            n += 5
            ans -= 1
        else:
            ans += n // 2
            break
            
else:
    if n % 2 == 0:
        ans = n // 2
    else:
        ans = -1
print(ans)

풀이2

주어진 거스름돈이 5의 배수라면, 가격을 5로 나눈 횟수가 거슬러줘야 하는 동전의 개수가 최소가 될 것이다. 따라서, 거스름돈을 5로 계속 나눠가면서, 만약 5로 나누어지지 않는다면, 2원을 한 번씩 거슬러주면 된다. 2원을 계속 거슬러주면서, 가격이 5의 배수가 되면 그 때 5원으로 전부 거슬러준다면 동전의 개수가 최소가 된다.
만약, 2원씩 거슬러 주는데, 가격이 마이너스가 된다면 이는 거슬러줄 수 없다는 것을 의미한다. (전부 2원으로만 거슬러 줄 수 있다면, 가격이 마지막에 0이 되고, 이는 while문을 탈출할 수 있게 된다)

코드2

# 백준 14916 다른 코드

n = int(input())

cnt = 0
i = 0
while True:
    if n % 5 == 0:   # 5의배수이면 5로 나눈 값이 최소의 동전 개수
        cnt += n//5		
        break
    else:
        n -= 2   #5의배수가 아니면 2원씩 계속 거슬러주면서 5의 배수가 되도록 설정
        cnt += 1

    if n < 0:  # 2원씩 거슬러주다가 음수가 된다면 거슬러줄 수 없음을 의미 
        break  # 만약 n == 0이면 2원으로만 거슬러줄 수 있음을 의미하고, 이는
               # 처음 if문의 탈출 조건이 성립됨
if n<0:			
    print(-1)			
else:
    print(cnt)