Pythonで所持コインで買えるアイスクリームの最大数を求めるプログラム

本記事では、Pythonを使って「所持しているコインで最大いくつのアイスクリームを買えるか」を求めるアルゴリズムを解説します。

問題の概要

n個の要素を持つ配列 costs が与えられます。costs[i] は i 番目のアイスクリームの価格（コイン単位）を表します。最初に c 枚のコインを持っており、できるだけ多くのアイスクリームを購入したいと考えます。このとき、c 枚のコインで買えるアイスクリームの最大数を求めるのが目的です。

たとえば、入力が costs = [3,1,4,5,2]、c = 10 の場合、出力は 4 になります。これは、インデックス 0、1、2、4 のアイスクリームを合計 3 + 1 + 4 + 2 = 10 コインで購入できるためです。

解き方のアプローチ

この問題は貪欲法（グリーディ法）で効率的に解けます。安いアイスクリームから順に買っていけば、同じ予算で最大数を達成できるためです。手順は以下の通りです。

• 配列 costs を昇順にソートする
• カウンタ変数 i := 0 を初期化する
• i が配列の長さ未満 かつ 残りのコイン c が costs[i] 以上である間、以下を繰り返す
  • c := c - costs[i]（コインを支払う）
  • i := i + 1（購入数を増やす）
• ループ終了後の i を返す（これが購入できた最大数）

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(costs, c):
   costs.sort()
   i = 0
   while(i < len(costs) and c >= costs[i]):
      c = c - costs[i]
      i = i + 1
   return i

costs = [3,1,4,5,2]
c = 10
print(solve(costs, c))

入力

[3,1,4,5,2], 10

出力

4

計算量について

このアルゴリズムの計算量は、ソートに O(n log n)、その後の走査に O(n) かかるため、全体として O(n log n) となります。ソートによって安価な商品から順に確認できるため、貪欲な選択が常に最適解につながる点がポイントです。