[백준] 14916번 거스름돈 (파이썬)

 

문제

 

14916번: 거스름돈

 

 

풀이 (Python)

 

n=int(input())
count=0

while n>=0:
    if n%5==0:                  #5로 나눠진다면 전부 다 나누기
        print(n//5+count)
        break
    n-=2                        #-2반복
    count+=1                    #2원을 거슬러 준 횟수를 count에 저장

if n<0:                         #n을 2를 빼고 5를 나누었을 때 떨어지지않는 경우 -1을 출력
    print(-1)

 

 

설명  (Python)

 

거스름돈 문제는 그리디알고리즘의 대표격의 문제라고 생각한다.

그리디 방식으로 풀이중에는 문제 풀이법에는 2가지 풀이가 있는데, 다른 풀이는 설탕배달 문제에서 풀이하겠다.

 

 

간단히 어떤 정수를 5원 또는 2원으로 거슬러 주면 되는 문제이다. 5원이나 2원을 통해서 거슬러 주지 못하는 경우에는 -1을 출력하면 된다.  처음 이와 같은 문제를 접했을 때는 굉장히 어렵게 느껴졌었다.

하지만 설탕배달 문제를 풀고난 후에 이 문제를 접하면 쉽게 느껴지고, 이 문제를 풀고 설탕문제를 풀면 쉽게 느껴지게 될것이다. 이 문제를 풀어봤다면 위의 설탕배달 문제도 풀어보는 것을 추천한다.

 

[백준] 2839번 설탕 배달 (파이썬)

 

 

어떤 n을 5원과 2원으로 최소 동전개수로 거슬러 주려면, 보통의 경우 5가 클 수록 동전의 개수가 줄어 든다.

하지만 무조건 5로 나누는 경우 5보다 작거나 5로 나누었을 때 나머지가 2로 안 떨어지는 경우를 처리하는데 매우 애먹게 되는데, 이때 while문을 통해 지속적으로 -2해주면서 5로 나누어질 수 있을 때 5로 나누어서 끝내는 로직이 굉장히 깔끔하다.

 

 

위의 로직을 통해 n에 -2를 반복하는데, 이때 n이 0보다 작아졌을 경우 5원과 2원으로 거슬러줄 수 없는 경우이기에 예외처리로 -1을 출력해주면 된다.