1. 문제 소개

1518. Water Bottles

2. 나의 풀이법

파이썬의 divmod()를 사용하면 몫과 나머지를 쉽게 구할 수 있다. 다음과 같이 풀어보았다.

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        answer = numBottles
        a, b = divmod(numBottles, numExchange)
        while a > 0:
            # print(a, b, answer)
            answer += a
            now = a + b
            a, b = divmod(now, numExchange)

        return answer

결과는 생각보다 안좋았다.
시간복잡도가 $O(log_{numExchange}(numBottles))$이기 때문인가?
1ms이내로 풀 수 있는 방법은 무엇일까?

3. 다른 풀이법

3.1. Editorial

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        consumed_bottles = 0

        while numBottles >= numExchange:
            # Consume numExchange full bottles.
            consumed_bottles += numExchange
            numBottles -= numExchange

            # Exchange them for one full bottle.
            numBottles += 1

        # Consume the remaining numBottles (less than numExchange).
        return consumed_bottles + numBottles

Editorial의 경우에는 divmod()가 아니라 단순한 +/-로 계산했다.
이 경우 시간복잡도는 $O(N)$으로 0ms로 나오게 된다.

3.2. Another Solution

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        return numBottles + (numBottles - 1) // (numExchange - 1)

그러나 다른 풀이의 경우 아예 수식으로 표현해 $O(1)$의 시간복잡도 해결했다.
이는 새로운 병 1개를 얻으려면 빈병 (numExchange - 1)개가 추가로 필요하다.
(왜냐하면 교환할 때마다 numExchange개가 필요하고, 새 병을 마시면 그 중 1개는 곧장 다시 빈병으로 되돌아오기 때문이다.)

따라서, 사용 가능한 빈병 (numBottles - 1)개를 (numExchange - 1)개씩 묶으면
$\left\lfloor \frac{\text{numBottles}-1}{\text{numExchange}-1} \right\rfloor$
만큼 추가 병을 얻을 수 있다.

4. 결론

나의 풀이법이 틀린 것은 아니지만, 더 나은 풀이법이 있다는 점에서 반성할만하다. 더 노력하자.