가득 찬 물병이 n개 있다고 가정해 봅시다. 빈 물병 m개를 내놓으면 가득 찬 물병 한 개로 교환할 수 있으며, 가득 찬 물병을 마시면 다시 빈 병이 됩니다. 이 문제의 목표는 총 마실 수 있는 물병의 최대 개수를 구하는 것입니다.
예를 들어 입력이 n = 9, m = 3이라면 출력은 13이 됩니다. 처음에 물병 9개가 있으므로 전부 마신 뒤 빈 병 9개로 9 ÷ 3 = 3개의 새 물병을 얻을 수 있습니다. 이 3개 역시 모두 마시면 빈 병 3개가 생기고, 이를 다시 교환하면 물병 1개를 추가로 마실 수 있습니다. 따라서 총 9 + 3 + 1 = 13개가 됩니다.
문제 해결 접근 방법
이 문제는 빈 병을 계속 교환하면서 남는 병을 추적하는 그리디 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
x := n, s := 0, k := 0 으로 초기화합니다.
x ≥ m 인 동안 아래를 반복합니다.
k := x mod m — 교환하고 난 뒤 남는 빈 병의 개수
x := x / m 의 몫 — 새로 얻은 가득 찬 물병의 개수
s := s + x — 마신 물병 수에 누적
x := x + k — 새 물병을 마셔 생긴 빈 병과 남은 빈 병을 합침
반복이 끝나면 n + s 를 반환합니다. (처음 마신 n개 + 교환으로 추가로 마신 s개)
예제 코드 (Python)
아래 파이썬 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
def solve(n, m): x = n s = 0 k = 0 while x >= m: k = x % m x = x // m s = s + x x = x + k return n + s n = 9 m = 3 print(solve(n, m))
입력
9, 3
출력
13
동작 원리 정리
핵심 아이디어는 간단합니다. 현재 가진 빈 병을 최대한 교환해 새 물병을 얻고, 그 물병을 마셔 생긴 빈 병에 이전에 교환하지 못하고 남은 빈 병을 더해 다시 교환을 시도하는 것입니다. 빈 병 수가 m보다 작아져 더 이상 교환할 수 없을 때까지 반복하면, 처음 마신 물병 수(n)와 교환으로 추가로 마신 물병 수(s)의 합이 곧 정답이 됩니다. 이 알고리즘의 시간 복잡도는 O(log_m n)으로 매우 효율적입니다.