백준 14916번 - '거스름돈' (PYTHON 풀이

문제:

 

5원과 2원이 무한정으로 있을 때, 동전을 최소화해서 거스름돈을 주어야 한다. 이때 지급한 동전의 총 개수를 구하는 문제이다.

 

풀이:

N = int(input())
count = 0

while N >= 0:
    if N % 5 == 0:
        count += N // 5
        print(count)
        break
    N -= 2
    count += 1
else:
    print(-1)

N에 지급해야할 거스름돈을 입력받고, 총 개수를 셀 count 변수를 초기화한다.

이후 N이 0 이상일 경우만 반복문을 돌도록 조건을 설정하고 만약 5로 나눠 떨어진다면 5로 나눈 몫을 바로 count에 넣어서 출력하고 반복문을 탈출한다. 5로 나눠 떨어진다는 의미는 예를 들어 15만큼 거스름돈을 줘야하고 5로 나눠떨어지면 동전의 개수는 3개만 필요하게 될 것이다. 즉 5의 배수면 5로 나눠 떨어진다는 의미이고 몫을 계산해서 바로 출력해주면 된다.

 

그러나 5로 나눠떨어지지 않을 경우에는 2씩 빼가면서 계산을 해주어야한다.(2원으로 지급해도 되기 때문) 그러다가 5로 나눠떨어지는 순간이 오면 앞서 말한 로직을 그대로 따라가게 되고, 5원과 2원으로 계산을 하다가 0보다 작아지는 순간이 오면 while문의 else가 실행되고 -1이 출력된다.

 

예시를 들어보겠다.

1) N = 13
13%5는 0이 아님(5로 나눠떨어지지 않음)
그럼 if문이 실행되지 않고, N-=2가 실행
-> 13-2=11 (count + 1)

11 또한 5로 나눠떨어지지 않음
-> 11-2=9 (count + 1)

9 또한 5로 나눠떨어지지 않음
-> 9-2=7 (count + 1)

7 또한 5로 나눠떨어지지 않음
-> 7-2=5 (count + 1)

5는 5로 나눠떨어짐!
if문이 실행되므로, count에는 5//5=1이 저장 (count + 1)

지금까지 count값은 1+1+1+1+1=5가 실행되고 break 실행!

2) N = 3
3%5는 0이 아님(5로 나눠떨어지지 않음)
그럼 if문이 실행되지 않고, N-=2가 실행
-> 3-2=1 (count + 1)

1 또한 5로 나눠떨어지지 않음
그럼 if문이 실행되지 않고, N-=2가 실행
-> 1-2=-1 (count + 1)

이제 N은 -1로 while문 조건이 성립되지 않으므로(0보다 작기 때문), 그대로 else문 실행이 되어 -1이 출력

 

위와 같은 로직으로 작동된다!