C++で解く「2キーキーボード」問題 ― 素因数分解で最小ステップ数を求める方法

テキストエディタには、最初は1文字の「A」だけが表示されているとします。この状態から、各ステップで次の2種類の操作を実行できます。

• すべてコピー(Copy All):メモ帳上にあるすべての文字をコピーします。
• 貼り付け(Paste):直前にコピーした文字を貼り付けます。

ここで整数 n が与えられたとき、最小の操作回数でメモ帳上にちょうど n 個の「A」を揃えることが目標です。つまり、n 個の「A」を得るために必要な最小ステップ数を求めるのがこの問題です。

例として n = 3 の場合を考えてみましょう。答えは 3 です。初期状態では「A」が1つしかないため、まずすべてコピーを行い、続けて貼り付けを実行すると「AA」になります。さらに貼り付けを1回行えば「AAA」となり、ちょうど3個の「A」が揃います。合計3ステップです。

解法のアプローチ

この問題を解く鍵は素因数分解の考え方です。n を素因数分解した際の各素因数の総和が、そのまま最小ステップ数になります。

たとえば n = 10 の場合、10 = 2 × 5 なので、答えは 2 + 5 = 7 です。これは「ある長さのブロックを1度コピーすれば、あとはそのブロック単位で一気に文字を増やせる」という性質によるものです。

具体的なアルゴリズムは以下の通りです。

• 答えを格納する変数 ret を 0 で初期化します。
• k を 2 から n まで順番に試します。
  • n が k で割り切れる間、ret に k を加算し、n を k で割り続けます。
• 最終的な ret の値を返します。

この処理は、本質的には n を素因数分解し、すべての素因数を足し合わせていることと同じです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minSteps(int n) {
        int ret = 0;
        for(int k = 2; k <= n; k++){
            for(; n % k == 0; ret += k, n /= k);
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.minSteps(10));
}

入力

10

出力

7

補足:計算量をさらに抑える工夫

上記のコードでは k を n までループしていますが、実際には √n まで確認するだけで十分です。ループ終了後も n > 1 が残っている場合は、それが n 自身の素因数であることを意味するため、その値を ret に加算すれば正しい答えが得られます。これにより、大きな n に対してもより高速に動作させることができます。