문제 설명
오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.
정답은 아무에게도 말하지 마세요.
콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?
단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.
문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다. 이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.
콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
1 ≤ b < a ≤ n ≤ 1,000,000
정답은 항상 int 범위를 넘지 않게 주어집니다.
입출력 예
a: 2, b: 1, n: 20, result: 19
문제 풀이
빈병을 콜라로 바꾼 후 바꾸지 못한 남은 빈병의 개수를 일반화할때, b가 2이상인 경우를 생각하면 일반화하기가 더 쉽다.
핵심은 콜라를 바꾸는 단계와 콜라를 마시는 단계를 한번에 처리하는 것이다. 다음번 콜라를 바꾸기 위한 빈병의 개수는 직전에 바꿨던 콜라의 개수(마시기만 하며 됨)와 남은 빈병의 개수를 더해주기만 하면 되기 때문이다. 생각해보면 콜라를 마시는 단계를 따로 생각할 필요조차 없다는 걸 알 수 있다.
def solution(a, b, n):
answer = 0
while n >= a:
cock=(n//a)*b # 빈병 n개로부터 콜라 cock 개 얻음
answer+=cock # 콜라 얻은 개수 누적합에 추가
emt=n%a # 사용되지 못한 빈병 개수
n = cock+emt # 콜라 마시고 다시 빈병 만들어진것 기존 빈병에 추가
return answer