코알라_3주차_백준_#1673_파이썬

문제

강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환할 수 있다.

강민이가 지금 갖고 있는 치킨 쿠폰으로 치킨을 최대 몇 마리나 먹을 수 있는지 구하여라. 단, 치킨을 주문하기 위해서는 반드시 치킨 쿠폰을 갖고 있어야 한다.

입력

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

출력

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

제한

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

예제 입력 1 복사

4 3
10 3
100 5

예제 출력 1 복사

5
14
124

 

 

<정답 코드>

import sys

for val in sys.stdin:
    n,k=map(int,val.split())
    chicken=0
    coupon=n
    stamps=0
    
    while coupon>0:
        chicken+=coupon
        stamps=coupon+(stamps%k)
        coupon=stamps//k

    print(chicken)

 

흥미로운 문제로 문제 조건을 잘 이해한 후 점화식을 잘 세운다면 쉽게 풀 수 있는 문제였다.

 

우선 현재 가지고 있는 쿠폰을 다쓰기 위해 배달을 시켜야 하므로

n번째 배달을 시켰을 때의 An=(이때 까지 다 먹은)치킨의 마리 수 , Bn=(현재)쿠폰의 수, Cn=(현재)도장의 수로 생각한다면

 

A(n+1)=An+B(n+1),

C(n+1)=B(n+1)+Cn&k,

B(n+1)=C(n+1)//k 로  생각할 수 있다.

 

여기서 중요한 포인트를 An을 n번째 배달을 시켰을 때 먹는 치킨의 마리 수가 아니라 이때 까지 다 먹은 치킨의 총합으로 두는 것이다.