【C++】3つの数値をすべてゼロにする最適なステップ数を求めるアルゴリズム

3つの整数が与えられているとします。この課題は、すべての数値を「0」にするために必要な最適な操作回数（ステップ数）を求めることです。

例

入力：

a = 4
b = 4
c = 6

出力：

7

解説：すべての数値を0にするまでの最適な手順は以下の通りです。

(4, 4, 6)

1つ目と2つ目の数値から1を引く → (3, 3, 6)

1つ目と3つ目の数値から1を引く → (2, 3, 5)

1つ目と3つ目の数値から1を引く → (1, 3, 4)

1つ目と3つ目の数値から1を引く → (0, 3, 3)

2つ目と3つ目の数値から1を引く → (0, 2, 2)

2つ目と3つ目の数値から1を引く → (0, 1, 1)

2つ目と3つ目の数値から1を引く → (0, 0, 0)

このように、すべての数値をゼロにするまでに必要なステップ数は「7」となります。

問題を解くためのアプローチ

この問題では、「残りの1つの数値よりも合計が大きくなるような2つの数値」を選び、そこから1ずつ引いていくという貪欲法（グリーディ法）の戦略を用います。これにより、すべての数値を0にするまでの最小ステップ数を効率的に計算できます。

• 3つの数値を入力として受け取ります。
• 2つの数値（たとえばaとb）の合計がcより大きく、かつa > 0、b > 0を満たす場合は、aとbからそれぞれ1を引きます。
• 最小のステップ数を計算し、その結果を返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int maxSteps(int a, int b, int c) {
    int res = 0;
    while (a + b > c and a > 0 and b > 0) {
        a--;
        b--;
        res++;
    }
    res += min(c, a + b);
    return res;
}
int main() {
    int a = 4;
    int b = 4;
    int c = 6;
    cout << maxSteps(a, b, c) << endl;
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

7

入力が a = 4、b = 4、c = 6 の場合、すべての数値をゼロにするには7ステップ必要となるため、プログラムは7を出力します。