【最安値】最安値を達成するには

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

この問題で【最安値】を求める最終問題！

問題概要

• 八百屋では 3種類のパック でりんごが売られている。

  • 小パック：x 個 a 円
  • 中パック：y 個 b 円
  • 大パック：z 個 c 円
    （条件：x < y < z かつ a < b < c）

• ちょうど n 個 でなくても n 個以上 になればOK。

• 目的：n 個以上のりんごを買うための 最小コスト を求める。

入力例:

9 2 100 3 125 5 200

出力例:

375

✅ 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, z, c] = lines[0].split(' ').map(Number);
    
    const size = n + z;
    const dp = Array(size).fill(Infinity);
    dp[0] = 0;
    
    for(let i = 1; i < size; 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);
        if (i >= z) dp[i] = Math.min(dp[i], dp[i-z] + c);
    }
    
    for(let i = size - 2; i >= 1; i--){
        dp[i] = Math.min(dp[i], dp[i+1]);
    }
    
    console.log(dp[n]);
});

1️⃣ DP 配列の用意

const size = n + z;
const dp = Array(size).fill(Infinity);
dp[0] = 0;

• size = n + z としているのは、
  「ちょうど n 個」ではなく「n 個以上」も許容するため、
  最大で z 個オーバーするケースも計算するため。
• dp[i]: 「ちょうど i 個買うときの最小コスト」
• 初期値は Infinity（未計算扱い）、dp[0] = 0（0個ならコスト0）

2️⃣ 順方向DP（必要数を作る）

for(let i = 1; i < size; 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);
  if (i >= z) dp[i] = Math.min(dp[i], dp[i-z] + c);
}

• 小さい個数から順に、
  • x個入りパックを使う場合の最小コスト
  • y個入りパックを使う場合の最小コスト
  • z個入りパックを使う場合の最小コスト　を更新していく。
• dp[i-x] + a は「i-x個を作ったコスト ＋ x個パックの価格」。

3️⃣ 逆方向の最適化（n個以上もOKにする）

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

• 例: n=10個必要でも、dp[12] が安いなら 12個買った方がお得な場合がある。
• 後ろから見て、
  「i個作るより i+1個作る方が安いなら、iのコストを更新」している。
• これにより「n個以上で最安」を保証。

4️⃣ 出力

console.log(dp[n]);

• 最終的に、n個以上を作る最小コストが dp[n] に入っている。

🗒️ まとめ

• 順方向DPで「ちょうどi個」の最小コストを作る。
• 逆方向更新で「n個以上でも良い」場合のコストを反映。
• n+z-1 まで配列を作るのは「最大パック数オーバー分」も考慮するため。

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

🔍 視覚化

今回の問題のコードの流れ・アルゴリズムを視覚化してわかりやすくしてみた！

例：

• n = 7,

• x = 3, a = 100,

• y = 4, b = 140,

• z = 6, c = 200

• dp[i] = i個のりんごを手に入れる最小コスト
• 初期値 dp[0] = 0、他は Infinity

順方向dp

個数 i	初期値	更新後のdp[i]	更新根拠
0	0	0	初期条件
1	∞		∞
2	∞	∞	到達不可
3	∞	100	dp[0] + a
4	∞	140	dp[0] + b
5	∞	∞	到達不可
6	∞	200	min(dp[0] + c, dp[3]+a)
7	∞	240	min(dp[3]+b, dp[4]+a)
8	∞	280	dp[4]+b,
…	…	…	…
12 (n + z -1)	∞	400	min(dp[6]+c, dp[8]+b, dp[9]+a)

逆方向dp

個数 i	更新前	更新後のdp[i]	更新根拠
0	0	0	初期条件
1	∞	100	min(dp[1], dp[2])
2	∞	100	min(dp[2], dp[3])
3	100	100	同下
4	140	140	同2つ下
5	∞	200	min(dp[5], dp[6])
6	200	200	同下
7	240	240	同下
8	280	380	同下
…	…	…	min(dp[i], dp[i+1])
11 (n + z -2)	380	380	min(dp[11], dp[12])
12	400	–	–

こうして、x,y,zの組み合わせで到達できない個数があっても埋められ、

n 個以上のりんごを買うための 最安値がわかる。