【DPメニュー】最安値を達成するには 1 (paizaランク B)-解答例-PHP編

2022年8月14日

【DPメニュー】> 【最安値】STEP: 1 最安値を達成するには 1 (paizaランク B 相当) [難易度: 1471 ±19]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

八百屋にて、りんご1個が a 円で、りんご2個が b 円で売られています。

りんごの買い方を工夫したとき、n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。

(ヒント)

りんご1つあたりの値段を計算し、安いほうのりんごを買うことで金額の最小値を達成することもできますが、練習だと思ってDPで解いてみましょう。

部分問題として、りんご i 個 (1 ≦ i ≦ n-1) を買うのに必要な金額の最小値を求める問題を考えてみましょう。これらの問題の答えがすべて分かっているとして、n 個のりんごを買うのに必要な金額の最小値はどうなるかを考えてみましょう。少し考えると、n 個のりんごを最も安く買う方法は、

n-1 個のりんごを最も安く買ってから最後に1個のりんごを a 円で買う
n-2 個のりんごを最も安く買ってから最後に2個のりんごを b 円で買う

の2通りのうち安いほうであることがわかります。なお、a < b という制約があるため、n-1 個のりんごを最も安く買ってから最後に1個買う代わりに2個買うのは常に無駄であることに注意しましょう。これで、部分問題と元の問題との関係が明らかになりました。dp[n] をちょうど n 個のりんごを買うのに必要な金額の最小値として、漸化式を立ててみましょう。

入力値（例）
5 100 150

出力値（例）
400

解答例

<?php
    list($n, $a, $b) = explode(" ", trim(fgets(STDIN)));
    
    $dp[0] = 0;
    $dp[1] = $a;
    
    for ($i = 2; $i <= $n; $i++) {
        $dp[$i] = min($dp[$i - 1] + $a, $dp[$i - 2] + $b);
    }
    
    echo $dp[$n];
?>

<?php

list($n, $a, $b) = explode(" ", trim(fgets(STDIN)));

$dp[0] = 0;

$dp[1] = $a;

for ($i = 2; $i <= $n; $i++) {

$dp[$i] = min($dp[$i - 1] + $a, $dp[$i - 2] + $b);

}

echo $dp[$n];

(ヒント)

解答例

カテゴリー