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

2022年8月15日

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

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

問題文

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

(ヒント)

前問の八百屋ではりんごが1個と2個で売られていましたが、本問の八百屋では2個と5個で売られています。この変更により、前問と同じようにして解こうとするとうまくいかなくなりました。理由を考えてみてください。

前問と同じように dp[n] をちょうど n 個のりんごを買うのに必要な金額の最小値とすると、dp[3] の値が正しく計算されないことがわかります。これは、りんごは2個ずつか5個ずつでしか買うことが出来ないため、3個のりんごをちょうど買う方法が存在しないからです。では、どうしたら dp[3] のような、2と5の組合せでは作れないような個数について最安値を計算することが出来るでしょうか。

問題文の最後の文に注目すると、買うりんごの数が3個以上になってもよいことがわかるので、ここで dp2[n] を n 個以上のりんごを買うのに必要な金額の最小値としてみましょう。dp と dp2 の定義から、dp2[n] = min(dp[n], dp[n+1], ...) であることがわかります。dp2[n] が求めたい答えになっています。

dp は dp[n] までではなく、余裕をもって dp[n+4] 程度まで計算しておく必要があることに注意しましょう (実はこの問題においては dp[n+2] まで計算しておけば十分なのですが、ある程度多めに計算しておくと安心です) 。また、実は新しく dp2 という配列を用意せずとも、dp をうまく書き換えることで答えを求めることもできます。余裕があれば考えてみてください (ヒント:ループを回す順番を工夫) 。

入力値（例）
4 110 200

出力値（例）
200

解答例

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

<?php

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

$dp[0] = 0;

for ($i = 1; $i <= ($n + 5); $i++) {

$dp_a = $i > 2 ? $dp[$i - 2] + $a : $a;

$dp_b = $i > 5 ? $dp[$i - 5] + $b : $b;

$dp[$i] = min($dp_a, $dp_b);

}

echo $dp[$n];

解説

この問題の漸化式は、dp[k] = min(dp[k - 2] + a, dp[k - 5] + b)となります。解答例では三項演算子を使いましたが、if()で書くと以下のようになります。

<?php    
    if ($i > 2) {
        $dp_a = $dp[$i - 2] + $a;
    } else {
        $dp_a = $a;
    }
    
    if ($i > 5) {
        $dp_b = $dp[$i - 5] + $b;
    } else {
        $dp = $b;
    }
?>

<?php

if ($i > 2) {

$dp_a = $dp[$i - 2] + $a;

} else {

$dp_a = $a;

}

if ($i > 5) {

$dp_b = $dp[$i - 5] + $b;

} else {

$dp = $b;

}

(ヒント)

解答例

解説

カテゴリー