▼感想:
りんごn個をセット単独購入する場合の最安値と、
りんごn個をセット組合せ購入する場合の最安値を計算し、
両者を比較して安いほうを最終的な最安値とします。
セット単独購入
- りんご2個a円セットのみ購入
- りんご5個b円セットのみ購入
セット組合せ購入
- りんご2個a円セットとりんご5個b円セットを組合せて購入
▼コード:
########## 処理0(準備) インプット,リスト定義など ###########
import math
n,a,b = map(int,input().split())
dp = [0]*(1000+1)
########## 処理1 漸化式の定義、計算、出力 ##########
dp[0] = 0
dp[1] = 0
# apx_cost: セット単独購入、セット組合せ購入の金額のうち最安値になりうる候補の金額を格納するリスト
apx_cost = []
for i in range(2,n+1):
########## 処理1.1 セット単独購入の金額のうち、最安値を計算する ##########
# ap2_num,ap5_num: りんご2個a円セット、りんご5個b円セットの購入数を格納する変数
# ap25_cost: セット単独購入の金額のうち最安値を格納する変数
ap2_num = math.ceil(i/2)
ap5_num = math.ceil(i/5)
ap25_cost = min(ap2_num*a,ap5_num*b)
apx_cost.append(ap25_cost)
########## 処理1.2 セット組合せ購入の金額のうち、最安値になりうる候補の金額を計算する ##########
for j in range(1,ap2_num+1):
for k in range(1,ap5_num+1):
# セット組合せのりんごの数がn個以上になった
if j*2 + k*5 >= n:
# ap25set_cost: セット組合せ購入の金額を格納する変数
ap25set_cost = j*a + k*b
# セット組合せ購入の金額が、セット単独購入の金額より安いならば
if ap25set_cost < ap25_cost:
apx_cost.append(ap25set_cost)
########## 処理1.3 セット単独購入、セット組合せ購入の金額のうち最安値を計算する ##########
dp[i] = min(apx_cost)
apx_cost.clear()
print(dp[n])
▼その他:
コードを書き終わった後に気づきましたが、
漸化式になっていないですかね...
dp[n]をdp[n-1]を用いて計算していませんでした。
確認したいと思います。