3100. Water Bottles II

numBottles와 numExchange가 주어짐
numBottles 개수 만큼의 병을 모두 마시고 empty 개수를 마신만큼 증가 시키며 마신 것의 개수를 증가 시킬 수 있음
혹은 empty 개수가 numExchange 이상인 경우 numExchange 개수 만큼의 empty 개수로 numBottles 하나를 증가하고 numExchange도 하나 증가할 수 있음

이렇게 해서 마신 개수가 최대가 되는 값을 찾기

class Solution:
    def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:

        def dfs(full, empty, exchange, drunk, mx):
            if full == 0 and empty < exchange:
                mx[0] = max(mx[0], drunk)
                return

            if full > 0:
                dfs(0, empty + full, exchange, drunk + full, mx)

            if empty >= exchange:
                dfs(full + 1, empty - exchange, exchange + 1, drunk, mx)

        mx = [0]
        dfs(numBottles, 0, numExchange, 0, mx)

        return mx[0]