Pythonでn日目までの銀行預金合計額を求めるプログラム

問題の概要

最初の日(月曜日)に銀行へ1ルピーを預けるとします。翌日の火曜日から日曜日にかけては、前の日より1ルピーずつ多く預けます。さらに、その後の毎週月曜日には、前の月曜日より1ルピー多く預けるものとします。

整数 n が与えられたとき、n 日目の終わりの時点で銀行にいくらのお金が貯まっているかを求めるのがこの問題です。

具体例

たとえば入力が n = 17 の場合、出力は 75 になります。その内訳は以下の通りです。

• 1週目：月曜日に1ルピー、火曜日に2ルピー……と順に増やしていき、日曜日には7ルピーを預けます。
• 2週目：月曜日に2ルピー、火曜日に3ルピー……と続き、日曜日には8ルピーを預けます。
• 3週目：月曜日に3ルピー、火曜日に4ルピー、そして最終日の水曜日には5ルピーを預けます。

したがって、合計は (1+2+3+4+5+6+7)+(2+3+4+5+6+7+8)+(3+4+5) = 75 ルピーとなります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• s を 28 に設定する(初週の合計 1+2+…+7 = 28)
• res を 0 に設定する
• n > 7 の場合:
  • res := s
  • div := n / 7 の切り捨て値(完全な週の数)
  • i が 1 から div−1 までの範囲で:res := res + s + 7×i
  • rem := n mod 7(端数の日数)
  • i が 1 から rem までの範囲で:res := res + i + div
• それ以外(n ≤ 7)の場合:
  • i が 1 から n までの範囲で:res := res + i
• res を返す

このアルゴリズムのポイントは、1週間ごとの預金合計が「28 ずつ」増えていく点です。初週の合計は 28 なので、2週目は 35、3週目は 42 というように等差数列になります。この性質を利用することで、すべての日を個別に足し合わせるよりも効率的に答えを求められます。

実装例(Python)

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

def solve(n):
    s = 28
    res = 0
    if n>7:
        res = s
        div = n//7
        for i in range(1,div):
            res += s+7*i
        rem = n % 7
        for i in range(1,rem+1):
            res += i+div
    else:
        for i in range(1,n+1):
            res+=i
    return res

n = 17
print(solve(n))

入力

17

出力

75