C++로 풀어보는 맥주병 교환 문제 – 마실 수 있는 맥주 총 개수 구하기

문제 이해하기

하나의 숫자 n이 주어지며, 이 값은 가득 찬 맥주병의 개수를 의미합니다. 빈 맥주병 3개를 모으면 새 맥주 1병으로 교환할 수 있을 때, 최종적으로 마실 수 있는 맥주의 총 개수를 구하는 것이 이 문제의 목표입니다.

예를 들어 입력이 10이라면 출력은 14가 됩니다.

왜 14일까요?

• 처음 10병을 모두 마시면 빈병 10개가 생기고, 누적 10병
• 빈병 9개로 새 맥주 3병을 교환해 마시면 누적 13병, 빈병은 1 + 3 = 4개
• 빈병 3개로 맥주 1병을 더 교환해 마시면 누적 14병, 남은 빈병 2개로는 더 이상 교환 불가

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• solve() 함수를 정의하고, 매개변수로 n을 받습니다.
• 결과값을 저장할 변수 ret을 0으로 초기화합니다.
• n이 3 이상인 동안 아래 과정을 반복합니다.
  • q := n / 3 (교환 가능한 묶음 수)
  • ret := ret + q * 3 (마신 병 수 누적)
  • n := n - q * 3 (사용한 빈병 제거)
  • n := n + q (교환해서 얻은 새 맥주 추가)
• 반복이 끝나면 ret := ret + n (더 이상 교환할 수 없는 나머지 병 마시기)
• ret을 반환합니다.

구현 예제

아래는 위 로직을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(int n) {
        int ret = 0;
        while(n >= 3){
            int q = n / 3;
            ret += q * 3;
            n -= q * 3;
            n += q;
        }
        ret += n;
        return ret;
    }
};
main() {
    Solution ob;
    cout << ob.solve(10);
}

입력

10

출력

14

정리

이 알고리즘은 매 반복마다 교환 가능한 만큼 맥주를 마시고, 그 결과로 얻은 새 맥주를 다시 계산에 포함하는 방식으로 동작합니다. 시간 복잡도는 O(log₃ n)으로 매우 효율적이며, 빈병 교환 비율만 바꾸면 다양한 변형 문제에도 쉽게 응용할 수 있습니다.