C++で合計値nを作るために必要な最小の文字数を求める方法

問題概要

整数 n が与えられ、アルファベットを a = 1、b = 2、c = 3、……、z = 26 というように数値に対応させます。このとき、対応する数値の合計がちょうど n になるようにするために必要な最小の文字数を求めるのが課題です。

各文字が表せる最大の値は z = 26 であるため、必要な文字数は「n を 26 で割って切り上げた値」になります。

入出力の例

入力: n = 23 → 出力: 1 （w = 23 で表現できるため）
入力: n = 72 → 出力: 3 （26 + 26 + 20 = 72）

アルゴリズム

考え方は非常にシンプルです。1文字あたり最大 26 までの値を担当できるので、次のように答えが決まります。

1. n が 26 で割り切れる場合：答えは n / 26
2. n が 26 で割り切れない場合：答えは n / 26 + 1（切り上げ）

つまり、これは数学における天井関数 ceil(n / 26) と同じ計算です。剰余が残っている限り、もう1文字追加してその分を補う必要があるためです。

C++での実装例

#include <iostream>
using namespace std;

int minRequiredSets(int n){
    if (n % 26 == 0) {
        return (n / 26);
    } else {
        return (n / 26) + 1;
    }
}

int main(){
    int n = 72;
    cout << "Minimum required sets: " << minRequiredSets(n) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum required sets: 3

計算量とポイント

このアルゴリズムの時間計算量は O(1)、空間計算量も O(1) であり、非常に効率的です。剰余演算と整数除算だけで答えが求まるため、大きな n に対しても即座に処理できます。

なお、より簡潔に書きたい場合は、条件分岐を使わずに (n + 25) / 26 という式でも同じ切り上げ計算を実現できます。