치킨 쿠폰

문제: 처음에 교환 쿠폰 n장이 있고, k장을 사용하면 1장의 쿠폰을 줄 때, 최대 몇 마리의 치킨을 받을 수 있는가?

 

 

사용한 총 쿠폰 수를 t라고 하자.

 

처음 n장이 있으니 t의 초기값은 n이다.

 

 

새로 받을 수 있는 쿠폰은 n // k 장이다. t += n // k

* 가지고 있는 쿠폰으로 최대한 많이 교환

 

이때 남는 쿠폰은 n // k + n % k 장이다. n = n % k + n // k

* 교환하지 못한 n % k 장 + 이제 새로 받은 n // k 장

 

이것을 새로 받을 수 있는 쿠폰이 0장이 될 때까지 반복하면 된다.

 

t = n
while n//k > 0:
    t += n//k
    n = n//k + n%k

 

 

이제 t를 한번에 구하자.

 

k개의 쿠폰을 사용하면 1개의 쿠폰을 받으므로, k - 1개의 쿠폰으로 치킨을 하나 받을 수 있다.

 

하지만 n // (k - 1) 은 n이 k - 1로 나누어 떨어질 때 문제가 발생한다.

 

쿠폰이 k - 1 장 남았을 때, 치킨을 일단 주문하고 받는 쿠폰으로 k개를 채워 거래하는 비상식적인 경우이다.

 

 

이런 경우는 n // (k - 1) - (n % (k - 1) == 0) 와 같이 처리해 줄 수 있다.

 

이는 (n - k) // (k - 1) + 1 과 동치이다.

 

 

조금 더 일반화하여 치킨을 하나 주문하면 c개의 쿠폰을 준다고 할 때,

 

(n - k) // (k - c) + 1 역시 성립한다.

 

 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    P, M, F, C = map(int, input().split())
    paidChicken = (M // P)
    s = d = 0

    d = paidChicken + (paidChicken*C)//F
    s = paidChicken
    if paidChicken*C >= F:
        s += (paidChicken*C - F) // (F - C) + 1
    print(s - d)

 

boj.kr/13199

13199번: 치킨 먹고 싶다