【C++】ちょうどnリットルの水を購入するための最小金額を求めるプログラム

3つの整数 n、a、b が与えられたとします。私たちは n リットルの水をちょうど購入したいと考えています。

近くの店で売られているのは、次の2種類の水のボトルだけです。

• 1リットル入りボトル:価格 a ルピー
• 2リットル入りボトル:価格 b ルピー

できるだけお金をかけずに済ませたいので、ちょうど n リットルの水を購入するために必要な最小金額を求めます。

入力例と出力例

たとえば、入力が n = 7、a = 3、b = 2 の場合、出力は 9 になります。

その理由は以下の通りです。

• 2リットルボトルを3本購入 → 6リットル分を6ルピーで確保
• 残り1リットルは1リットルボトルを1本購入 → 3ルピー

合計金額は 6 + 3 = 9 ルピーとなり、これが最小の支払額です。

解法のアプローチ

この問題は貪欲法(グリーディ法)でシンプルに解くことができます。ポイントは次の通りです。

1. まず、「2リットルボトル1本の価格 b」と「1リットルボトル2本の価格 a × 2」を比較し、安い方を2リットルあたりの実効価格として採用します。これにより、1リットルボトル2本の方が安いケースにも対応できます。
2. n を2で割った商の分だけ2リットルボトルを購入し、n が奇数の場合は余りの1リットルを1リットルボトルで補います。

アルゴリズムの手順

b := min(a * 2, b)
return (n / 2 * b) + (n mod 2) * a

C++での実装例

以下に、実際のC++コードを示します。

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

int solve(int n, int a, int b) {
    // 2リットル分のコストは、2リットルボトル1本か1リットルボトル2本の安い方
    b = min(a * 2, b);
    // 2リットルボトルで n/2 本分を買い、奇数なら残り1リットルを1リットルボトルで補う
    return n / 2 * b + n % 2 * a;
}

int main() {
    int n = 7;
    int a = 3;
    int b = 2;
    cout << solve(n, a, b) << endl;
}

入力

7, 3, 2

出力

9

計算量について

このアルゴリズムは比較と四則演算を定数回行うだけでよいため、時間計算量 O(1)、空間計算量 O(1) で動作します。n がどれほど大きくなっても高速に答えを求められるのが特徴です。