C++で解くビール瓶交換問題：空き瓶3本で1本と交換できるときに飲める本数を求める

この記事では、C++を使って「ビール瓶の交換問題」を解くアルゴリズムを紹介します。数値 n が与えられ、これは満杯のビール瓶が n 本あることを表します。空き瓶3本を満杯のビール瓶1本と交換できる場合、最終的に何本のビールが飲めるかを求めるのが目的です。

例えば、入力が 10 の場合、出力は 14 になります。

問題の流れ

10本の場合を具体的に見てみましょう。

• まず10本すべて飲みます（合計10本）。空き瓶が10本できます。
• 空き瓶9本を交換して、満杯の瓶3本をもらいます。さらに3本飲みます（合計13本）。
• この時点で空き瓶は残り1本＋新たな3本＝4本です。
• うち3本を交換して1本もらい、飲みます（合計14本）。
• 最後に空き瓶が2本残りますが、これ以上は交換できません。

したがって、答えは14本となります。

解法のアプローチ

この問題は以下の手順で解くことができます。

• solve() 関数を定義し、引数として n を受け取ります。
• 結果を格納する変数 ret を 0 で初期化します。
• n が 3 以上である限り、次の処理を繰り返します。
  • q = n / 3（交換できる回数）を計算します。
  • ret に q × 3 を加算します（実際に飲んだ本数）。
  • n から q × 3 を減算し、使用済みの空き瓶を取り除きます。
  • n に q を加算します（交換でもらった新しい瓶）。
• ループ終了後、余った n 本を ret に加算します。
• ret を返します。

C++での実装例

それでは、上記のロジックを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

まとめ

このアルゴリズムは、while ループによって空き瓶が3本未満になるまで交換を繰り返すシンプルな構造になっています。整数除算（n / 3）を使うことで、一度に何セット交換できるかを効率的に計算でき、計算量も少なく実用的な実装となっています。同様の「交換・還元」系の問題（例えば、コーラの空き缶交換など）にも応用できる考え方なので、ぜひ覚えておきましょう。