合計kを作るために必要な最小コイン枚数を求めるC++プログラム

問題概要

2つの整数 n と k が与えられます。価値が 1 から n までのコインを無限に持っているものとします。これらのコインを組み合わせて合計をちょうど k にしたいのですが、同じ価値のコインは何枚でも繰り返し使えます。このとき、合計 k を作るために必要なコインの最小枚数を求めましょう。

例えば、n = 6、k = 16 が入力された場合、出力は 3 となります。これは「価値 6 のコイン 2 枚」と「価値 4 のコイン 1 枚」を組み合わせて (2 × 6) + 4 = 16 が達成できるためです。

解法の考え方

この問題は O(1) の定数時間で解くことができます。ポイントは、価値 1 から n までのすべてのコインが利用可能であるという点です。

まず、枚数を最小化するには価値 n のコインをできる限り多く使うのが得策です。k ÷ n の商の分だけ価値 n のコインを使うと、余り r = k mod n が残ります。r が 0 でなければ、価値 r のコインは必ず存在する(1 ≤ r ≤ n−1 < n であるため)ので、残りはたった 1 枚で支払えます。したがって、求める答えは「k を n で割った値の切り上げ」、すなわち ceil(k / n) です。

C++の整数除算では小数点以下が切り捨てられるため、切り上げ計算は次の定番テクニックで実現します。

c := (n + k - 1) / n
return c

割る前に (n + k − 1) を加えておくことで、余りが存在する場合にのみ結果が 1 増え、数学的に正確な切り上げ除算が行われます。

C++での実装例

#include<bits/stdc++.h>
using namespace std;

int solve(int n, int k){
    int c = (n + k - 1) / n;
    return c;
}

int main(){
    int n = 6;
    int k = 16;
    cout << solve(n, k) << endl;
}

入力

6, 16

出力

3

まとめ

価値 1 〜 n のコインが無限にある場合、合計 k に必要な最小コイン枚数は ceil(k / n) で表せます。C++では (n + k - 1) / n という切り上げ除算のイディオムを使えば、ループ不要の定数時間で簡潔に答えを導き出せます。