BOJ 1673 - 치킨 쿠폰

문제

BOJ 1673 - 치킨 쿠폰

치킨 n마리를 구매하면 쿠폰 n장을 받고, 쿠폰 k장을 모으면 치킨 1마리로 교환할 수 있다. 교환한 치킨에서도 쿠폰이 나올 때, 총 먹을 수 있는 치킨 수를 구하라 (EOF까지 반복).

입력

여러 테스트 케이스가 주어지며, 각 줄에 n과 k가 주어진다 (EOF까지).

출력

각 테스트 케이스마다 먹을 수 있는 치킨의 총 수를 출력한다.

예제

풀이

초기 쿠폰 n장에서 시작하여 k장당 1마리를 교환하는 시뮬레이션을 반복한다.

1. 처음 n마리를 먹고 쿠폰 n장을 모은다
2. 쿠폰이 k장 이상인 동안: 교환 가능한 치킨 수(n // k)를 더하고, 남은 쿠폰(n % k)과 교환으로 받은 쿠폰(n // k)을 합산하여 새 쿠폰 수로 갱신한다
3. 더 이상 교환이 불가능하면 총 치킨 수를 출력한다
4. EOF까지 반복 처리한다

핵심 아이디어: 교환한 치킨에서도 쿠폰이 나오므로 재귀적으로 교환이 가능하며, 매 반복에서 쿠폰이 1/k로 줄어들어 O(log_k(N))에 종료한다.

코드

while True:
    try:
        y = 0
        n, k = map(int, input().split())
        y += n
        while n // k:
            y += n // k
            n = n // k + n % k
        print(y)
    except:
        break

복잡도

• 시간: O(log_k(N))
• 공간: O(1)