最安値を達成するには 3

今回は paiza の DP で「最安値を達成するには 3」の問題に挑戦！

前回 学んだことを使って解くことができる！

問題概要

• 2種類のりんごセットがある。

  • x 個入り … 価格 a 円
  • y 個入り … 価格 b 円

• 条件として x < y かつ a < b が保証されている。

• 目標: 最終的に n 個以上 のりんごを手に入れるとき、支払う金額の最小値を求める。

  • ぴったり n 個でなくても、n+1 個以上になってもよい。

入力例:

4 2 110 5 200 // n x a y b

出力例:

200

✅OK例：

const rl = require('readline').createInterface({ input:process.stdin});

const lines = [];

rl.on('line', (input) => lines.push(input));


rl.on('close', () => {
    const [n, x, a, y, b] = lines[0].split(' ').map(Number);
    
    const dp = Array(n + y).fill(Infinity);
    dp[0] = 0;
    
    for(let i = 1; i < n + y; i++){
        if (i >= x) dp[i] = Math.min(dp[i], dp[i-x] + a);
        if (i >= y) dp[i] = Math.min(dp[i], dp[i-y] + b);
    }
    
    for(let j =  n + y - 2; j >= 1; j--){
        dp[j] = Math.min(dp[j], dp[j+1]);
    }
    
    console.log(dp[n]);
});

① dp配列の意味

dp[i] = 「りんごをちょうど i 個買うための最小金額」

最初は全部 Infinity（最大値）にして、dp[0] = 0（0個は0円）で初期化。

② 小さい個数から順に計算

for (let i = 1; i < n + y; i++) { 
  if (i >= x) dp[i] = Math.min(dp[i], dp[i-x] + a);
  if (i >= y) dp[i] = Math.min(dp[i], dp[i-y] + b);
}

• 「x個入りを1つ追加する場合」と「y個入りを1つ追加する場合」を比べながら最小値を更新。
• これで「ちょうど i 個」の最安値が求まる。

③ n個以上を許容するための後ろから更新

for (let j = n + y - 2; j >= 1; j--) {
  dp[j] = Math.min(dp[j], dp[j+1]);
}

• n個ちょうど買えなくても、n+1個、n+2個…の方が安い可能性がある。
• そこで後ろから順に「より多く買った場合の金額」と比較して更新。
• こうすると dp[n] は「n個以上買う最安値」になる。

このコードは、

①まず「ちょうど買う場合の最安値」を求めて、
②その後「n個以上買う場合の最安値」に変換している、

という2段階構成になっている。

📝めも

• 問題の本質は「n 個以上」買う最小コストを求めること（ぴったり n 個でなくてOK）。

• 小さいセットと大きいセットの組み合わせで必要数を超えるケースも考慮する必要がある。

• DP配列 dp[i] を「i個ちょうど買うときの最小コスト」として、
  dp[i] = min(dp[i – x] + a, dp[i – y] + b) の形で小さい方から計算する。

• 「ちょうど n 個」だけだと不十分なので、後ろから走査して
  dp[i] = min(dp[i], dp[i + 1]) として「i個以上買うときの最小コスト」に更新する。

• この後処理により、dp[n] が「n 個以上買うときの最小金額」になりこの問題で求めたい最小値を導き出せる。

僕の失敗談(´;ω;｀)と解決法🐈