【Python】コインで作れる連続値の最大数を求めるプログラム

n個の要素を持つ配列 coins があり、これは私たちが所有しているコインを表しています。i番目のコインの価値は coins[i] で示されます。n枚のコインの中からいくつかを選び、その価値の合計がxになるようにできるとき、「値xを作ることができる」と定義します。このとき、0から始まる連続した値について、コインで作ることができる最大の連続値の個数を求めるのが本記事の目的です。

問題の例

たとえば、入力が coins = [1,1,3,4] の場合、出力は 10 になります。これは次のように、0から9までのすべての値を作れるためです。

• 0 = []

• 1 = [1]

• 2 = [1,1]

• 3 = [3]

• 4 = [4]

• 5 = [4,1]

• 6 = [4,1,1]

• 7 = [4,3]

• 8 = [4,3,1]

• 9 = [4,3,1,1]

解法のアプローチ（貪欲法）

この問題は、ソートと貪欲法（グリーディ法）を組み合わせることで効率的に解けます。手順は以下のとおりです。

• リスト coins を昇順にソートする

• ans := 1 と初期化する（現時点で0〜ans-1までの値が作れることを意味する）

• 各コイン coin について以下を繰り返す：

  • coin > ans の場合はループを抜ける

  • そうでなければ ans := ans + coin と更新する

• 最後に ans を返す

なぜこのアルゴリズムが正しいのか

現在「0からans-1までのすべての値」が作れる状態を考えてみましょう。ここに新しいコインcを追加するとき、c ≤ ans であれば、既存の組み合わせにcを足すことで「cからans+c-1まで」も作れるようになり、範囲が [0, ans+c) に拡張されます。一方、c > ans の場合、値 ans を作る手段が存在せず、そこにギャップが生じます。ソート済みなので以降のコインはさらに大きく、ギャップを埋めることはできません。したがって、その時点の ans が答えになります。

実装例

それでは、理解を深めるために実際の実装を見てみましょう。

def solve(coins):
    coins.sort()
    ans = 1
    for coin in coins:
        if coin > ans:
            break
        ans += coin
    return ans

coins = [1,1,3,4]
print(solve(coins))

入力

[1,1,3,4]

出力

10

計算量は、ソートにO(n log n)、走査にO(n)となるため、全体としてO(n log n)で非常に効率的です。