C++でn人分の折り紙招待状に必要なノートの最小冊数を求める方法

2つの整数 n と k が与えられたとします。パーティーには n 人の友人を招待する予定で、Amalさんは折り紙を使って招待状を作りたいと考えています。招待状1枚につき、赤い紙が2枚、緑の紙が5枚、青い紙が8枚必要です。各色のノートは無限にありますが、1冊のノートには1色のみで k 枚の紙が綴じられています。このとき、n 人全員を招待するためにAmalが購入すべきノートの最小冊数を求めます。

例えば、入力が n = 3、k = 5 の場合、出力は 10 になります。これは、赤のノートが2冊、緑のノートが3冊、青のノートが5冊必要だからです。

解法のアプローチ

この問題を解くには、次の手順に従います。

まず、必要な紙の枚数を色ごとに計算します。赤は 2×n 枚、緑は 5×n 枚、青は 8×n 枚です。次に、1冊あたり k 枚入りのノートでこれらの紙をまかなうため、切り上げ除算を利用します。「(必要な枚数 + k − 1) ÷ k」を計算すると、各色ごとに必要なノートの最小冊数が求められます。最後に、3色分の冊数を合計したものが答えとなります。

(2 * n + k - 1) / k + (5 * n + k - 1) / k + (8 * n + k - 1) / k

例として n = 3、k = 5 の場合を確認してみましょう。赤は 6 枚必要なので 6÷5 の切り上げで 2 冊、緑は 15 枚なので 3 冊、青は 24 枚なので切り上げて 5 冊。合計 2 + 3 + 5 = 10 冊となり、期待どおりの結果が得られます。

実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(int n, int k){
   return (2 * n + k - 1) / k + (5 * n + k - 1) / k + (8 * n + k - 1) / k;
}
int main(){
   int n = 3;
   int k = 5;
   cout << solve(n, k) << endl;
}

入力

3,5

出力

10

このように、切り上げ除算の公式を活用することで、色ごとのノート冊数を簡単かつ効率的に計算できます。計算量は O(1) と一定であり、n や k が大きくなっても高速に動作する点が魅力です。