문제 출처

분명 별로 어렵지 않은 문제인데 생각보다 헷갈렸다. 그러다 다른 사람의 풀이를 보니 신박한 방법이 있어 따로 작성한다.

일반적인 풀이

내가 가지고 있는 콜라병의 개수를 bottle_cnt라는 변수에 저장하자. bottle_cnt의 초기값은 문제에서 주어진 n이고, 이 변수의 변화를 따라가면 문제를 풀 수 있다.

문제에서 언급했듯이 내가 가진 병의 개수가 a 보다 적으면 안되므로 이를 반복문의 조건으로 설정한다.

while bottle_cnt >= a:
	pass

a개당 b개로 바꿔주므로 bottle_cnt를 a로 나눠준 몫을 cnt라는 변수에 저장하고 변화를 따라가보자.

while bottle_cnt >= a:
	cnt = bottle_cnt // a
    pass

bottle_cnt는 cnt * a만큼 줄어들고, cnt * b만큼 늘어난다. 이때 늘어난 양은 answer에 기록하자.

answer = 0
while bottle_cnt >= a:
	cnt = bottle_cnt // a
    bottle_cnt -= cnt * a
    bottle_cnt += cnt * b
    answer += cnt * b

위 코드에서 4번째 줄과 5번째 줄은 합쳐서 표현할 수 있다. 그것까지 완료하면 문제 풀이는 끝이다.

정답

def solution(a, b, n):
    answer = 0
    bottle_cnt = n
    while bottle_cnt >= a:
        cnt = bottle_cnt // a
        bottle_cnt += cnt * (b - a)
        answer += cnt * b
    return answer

신박한 풀이

풀이 출처

solution = lambda a, b, n: max(n - b, 0) // (a - b) * b

남의 풀이를 보니 신기한 풀이가 있었다. 감사하게도 해당 코드의 작성자가 이유를 설명해서 여기에 나도 작성한다.

$x$번 교환을 완료한 후 내가 가지고 있는 병의 개수를 $A_x$라고 하자. 한 번 교환을 할 때 a개를 주고 b개를 받으므로 이를 수식으로 정리하면 다음과 같다.

따라서 $A_x$는 초항이 $n$이고 등차가 $-(a-b)$인 등차수열이다.

문제에서 내가 가지고 있는 병의 개수가 a개 미만일 때까지 교환을 반복한다고 했으므로 $A_x \lt a$를 만족하는 최소의 $x$를 찾는 것이 풀이의 핵심이다. 이를 만족하는 $x$를 구하면 이는 교환의 총 횟수이므로 문제의 정답은 $\left( b - a \right) \times x$가 된다.

위 부등식에서 $x$는 자연수라는 조건이 있으므로 결국 n-a를 a-b로 나눈 몫에 $1$을 더한 수라는 것을 알 수 있다.

x = (n - a) // (a - b) + 1

따라서 정답은 ((n - a) // (a - b) + 1) * b, 다르게 정리하면 ((n - b) // (a - b)) * b가 된다.

정답

def solution(a, b, n):
    return ((n - b) // (a - b)) * b