C++でテレビの音量を元の値に戻すための最小ボタン操作回数を求める方法

2つの整数 a と b があるとします。Amalはいつもテレビの音量を「b」に設定していますが、ある日Bimalが誤って「a」に変更してしまいました。

リモコンには -5、-2、-1、1、2、5 の6つのボタンがあり、これらを使って音量を1、2、または5だけ増減できます。音量は非常に大きな値になり得ますが、負の値にはなりません。ここで、Amalが音量を再び「b」に戻すために必要な最小のボタン押下回数を求めるのがこの問題です。

問題の例

例えば、入力が a = 5、b = 14 の場合、出力は 3 になります。これは、「+5」を1回押して10にし、続いて「+2」を2回押して14に到達できるためです。

解法のアプローチ

この問題は貪欲法(グリーディ法)で効率的に解くことができます。まず、現在の音量と目標の音量の差の絶対値 d を計算し、次の式で最小押下回数を求めます。

d := |a - b|
return (d / 5 + (d mod 5 + 1) / 2)

この式の仕組みは以下のとおりです。

• d / 5: 「±5」ボタンを押す回数。できるだけ大きなステップを使うことで操作回数を抑えます。
• (d % 5 + 1) / 2: 残りの差を埋めるための追加回数。余りが1または2なら1回、3または4なら2回の操作で対応できます。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b){
    int d = abs(a - b);
    return (d / 5 + (d % 5 + 1) / 2);
}
int main(){
    int a = 5;
    int b = 14;
    cout << solve(a, b) << endl;
}

入力

5, 14

出力

3

動作の解説

d = |5 − 14| = 9 となります。「9 ÷ 5 = 1」なので「+5」を1回押し、「(9 % 5 + 1) ÷ 2 = (4 + 1) ÷ 2 = 2」なので残りの差4を「+2」を2回押して埋めます。したがって、合計3回のボタン操作で音量を目的の値に戻せることになります。