Pythonでリストの合計を目標値に一致させるために必要な最小の要素追加回数を求めるプログラム

問題の概要

数値のリスト nums と、2つの変数 k、t(ターゲット値)が与えられます。ここで「範囲 [-k, k] 内から任意の数 e を選び、リスト nums の末尾に追加する」という操作を考えます。この操作を繰り返して nums の合計をターゲット値 t と一致させるとき、必要となる最小の操作回数を求めるのがこの問題の目的です。

例えば、nums = [3, 1]、k = 4、t = 19 という入力の場合、出力は 4 になります。これは [4, 4, 4, 3] の順に要素を追加することで、合計が 3 + 1 + 4 + 4 + 4 + 3 = 19 となり、目標に到達できるためです。

解法のアプローチ

この問題は、シンプルな数学的な発想で効率よく解くことができます。手順は以下の通りです。

• nums に含まれる全要素の合計 total を求める
• ターゲットとの差 diff = |t − total| を計算する
• result を diff を k で割った商(小数点以下切り捨て)とする
• result × k が diff と等しくない場合(割り切れない場合)、result に 1 を加える
• result を返す

ポイントは、1回の操作で最大 k だけ合計を増減できるため、「目標との差分」を「1回あたりの最大変化量 k」で割り、余りが出たら切り上げるだけで答えが求まるという点です。これは天井関数(ceil)による計算と同等であり、計算量は O(n)(合計を求める部分)のみで非常に高速です。

実装例(Python)

以下は上記の手順を Python で実装したコードです。

def solve(nums, k, t):
    total = sum(nums)

    diff = abs(t - total)
    result = diff // k

    if result * k != diff:
        result = result + 1

    return result

nums = [3, 1]
k = 4
t = 19
print(solve(nums, k, t))

入力

[3, 1], 4, 19

出力

4

補足:math.ceil を使ったより簡潔な書き方

Python の標準ライブラリ math モジュールにある ceil 関数を使うと、割り算の切り上げ処理を1行で表現できます。

import math

def solve(nums, k, t):
    return math.ceil(abs(t - sum(nums)) / k)

どちらの実装でも結果は同じですが、ceil を使う方が意図が明確で読みやすいコードになります。競技プログラミングやコーディング面接では、このような「差分を最大ステップ幅で割って切り上げる」という発想は頻出テクニックなので、ぜひ覚えておきましょう。