백준 > Python3 > 1673번 : 치킨 쿠폰

이번 포스팅은 1673번의 치킨 쿠폰이라는 문제입니다.

사용언어는 파이썬입니다.

 

문제

강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다.

이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데,

도장을 k개 모으면 치킨 쿠폰 한 장으로 교환할 수 있다.

강민이가 지금 갖고 있는 치킨 쿠폰으로 치킨을

최대 몇 마리나 먹을 수 있는지 구하여라.

단, 치킨을 주문하기 위해서는 반드시 치킨 쿠폰을 갖고 있어야 한다.

 

입력/출력/제한

입력

여러 줄에 걸쳐서 자연수 n과 k가 주어진다.

출력

각 입력마다 한 줄에 정답을 출력한다.

제한

1 < k ≤ n ≤ 1,000,000,000

예제입력1	예제출력1
4 3 10 3 100 5	5 14  124

풀이

쿠폰으로 치킨을 먹을 수 있다는군요!

쿠폰 하나로 치킨 한마리를 교환할 수 있다고 합니다.

그리고 쿠폰으로 몇 마리를 사먹게 되면 쿠폰을 한장 더 준다고 하네요.

쿠폰으로 사먹었는데! 또 쿠폰을 주다니. 착한 가게.

 

첫번째 예제 케이스는 너무 쉽고!

두번째를 보시면 현재 가지고 있는 쿠폰의 수는 10개이고

3마리를 시키면 쿠폰을 하나 더 준다고 하네요.

 

일단 세마리를 시켜먹었다고 한다면 쿠폰을 3개를 쓰게 되겠죠?

남아있는 쿠폰은 7개가 됩니다. 하지만! 우리는 3마리를 사먹었으니

쿠폰을 하나 더 받아내야겠죠?? 우리는 흑우가 될 수 없습니닷!

 

그러면 남은 쿠폰의 수는 8개입니다.

8개나 남았으니 또 3마리를 시켜먹읍시다.

그러면 또 쿠폰을 받을 수 있어서 쿠폰이 6개가 남게 됩니다.

 

10개가 있던 쿠폰이 6개가 되었고

우리고 사먹은 치킨의 수는 6마리가 되었습니다.

 

이런 방식으로 나아가면 가장 간단하게 결과값을 구하는 방식입니다.

 

하지만 우리는 좀 더 빠르게 계산하는 방법을 알아봐요!

 

딱 떠오르는 방법은 한번에 최대한 많은 양의 치킨을 시키는거게요!

앞서 우리는 쿠폰을 하나 받을 수 있는 양만큼의 치킨을 시켰어요.

하지만! 더 많이 시킨다면 치킨을 시키는 횟수가 줄어들겠죠??

 

다시 예제케이스를 본다면

이번에는 9마리를 시켜버리자구요! 그러면 쿠폰을 9개를 사용하고

보너스로 쿠폰을 3개를 받게 됩니다.

그러면 우리가 먹은 치킨은 9마리가 되고

남은 쿠폰의 수는 4개가 되네요!

 

이번에는 3개밖에 주문을 못하는군요. 6개를 주문하고 싶지만

저희가 가진 쿠폰의 수는 4개밖에 안되니 3개 밖에 주문이 안되네요.

 

이렇게 주문을 우리가 가진 쿠폰의 수가

보너스 쿠폰을 받을 수 있는 수보다 작아질때까지 반복하면 되요.

그럼 이제 0 =< n < k 인 n개의 쿠폰이 남겠죠?

그러면 이 쿠폰으로 마져 치킨을 시켜서 다 소모시켜주게되면

남은 쿠폰은 0으로 더 이상 쿠폰을 시킬 수가 없게되요.

 

위의 과정을 코드로 구현해주시면 되겠죠??

 

import sys

for i in sys.stdin.readlines():
    n,k=map(int,i.strip().split())
    t=0
    r=0
    while n>=k:
        t=n//k
        r+=k*t
        n=n%k+t
    r+=n
    print(r)

 

https://www.acmicpc.net/problem/1673

1673번: 치킨 쿠폰