最安値を達成するには 2

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

前回と同じようにスムーズにはいかなくて面白かった！

問題概要

• 八百屋では、
  • りんご2個パック → a 円
  • りんご5個パック → b 円
    で販売されている。

• n 個のりんごが欲しいが、
  n 個ぴったりでなくてもよく、n 個以上あればよい。

• 目標は 最小の金額を求めること。

入力例：

4 110 200

出力例：

200

❌NG例：

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

const lines = [];

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


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

dp[i-5] が負インデックスや undefined になる場合の処理がない。

✅OK例：

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

const lines = [];

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


rl.on('close', () => {
    const [n, a, b] = lines[0].split(' ').map(Number);
    
    const dp = [];
    dp[0] = 0;
    dp[1] = a;
    dp[2] = a;
    
    for(let i = 3; i <= n; i++){
        const A = dp[i-2] + a;
        const B = (dp[i-5] + b || b);
        
        dp[i] = Math.min(A, B);
    }
    
    console.log(dp[n]);
});

dp[i-5] が undefined になる場合がある → || b のように初期購入を考慮してみた。

• 「"あと 2 個セットを買えばいいときの最安値"に a を足す」

• 「"あと 5 個セット買えばいいときの最安値"に b を足す」

という式の遷移になっているので、

dp[i] は 「i 個のりんごを買うための最安値」 を表すようになっており、結果として dp[n] が問題の答えになるという考え方。

✨改善例：

const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line));


rl.on('close', () => {
  const [n, a, b] = lines[0].split(' ').map(Number);
  
  const INF = 1e15;
  const size = n + 5;


  const dp = new Array(size).fill(INF);
  dp[0] = 0; 

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

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

  console.log(dp[n]);
});

🔍解説・全体の目的

2個パック（価格 a）と5個パック（価格 b）を組み合わせて、
「n 個以上のリンゴを買うための最小金額」を求める。

処理の流れ

① 初期化

const INF = 1e15; // 実質「無限大」扱いの大きな値
const size = n + 5; // n個以上をカバーする
const dp = new Array(size).fill(INF);
dp[0] = 0;

• dp[i] を「ちょうど i 個買うための最小金額」と定義。
• 最初は全部「非常に大きな値（到達不能）」で初期化。
• dp[0] = 0（0個ならコスト0円）。

② 「ちょうど i 個」を求めるDP

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

小さい方から順に計算して、

• 2個パック追加 → dp[i-2] + a
• 5個パック追加 → dp[i-5] + b
  のうち安い方を反映。

この時点では「ちょうど i 個」の最小コストのみを保持している。

しかし、2と５の組み合わせで、ちょうど i 個作れるとは限らない。

③ 「n 個以上」に変換

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

後ろから前に向かって更新することで
dp[i] を「i 個以上買うための最小金額」に変換。

理由：

• dp[i+1] は「i+1 個以上」の最小コスト
• dp[i] は「ちょうど i 個」の最小コスト
  → Math.min(dp[i], dp[i+1]) で「i 個以上」の最小コストが得られる。

※ 逆順で回す理由は、dp[i+1] がすでに「以上」に更新済みである必要があるため。

④出力

console.log(dp[n]);

最終的に dp[n] が「n 個以上買うための最小金額」になっている。

このコードのポイント

• 二段階DP
  • 段階1：ちょうど i 個の最小コストを計算
  • 段階2：それを「以上」に変換

• 安全な初期化
  • 大きな値（INF）で埋めて「未到達」状態を表現
  • dp[i-2] や dp[i-5] が未定義になることを防ぐ

• 逆順ループでの min 更新
  • 「以上」に変換するためには後ろから更新する必要がある

• n+5 まで計算
  • n 個以上を買うために最大4個余る場合がある
    → n+4 まで見れば十分安全（n+5 は余裕を持たせた形）

この書き方だと、すべてのパターンを網羅的に計算できるので、取りこぼしがないのが最大のメリット。

📝学習のまとめ

• dp[0] ~ dp[i-1] と dp[i] の関係は
  dp[i] = Math.min(dp[i-2] + a, dp[i-5] + b) となり、
  まずはこの漸化式に従って dp を小さい方から順に計算する。

• しかし、このままでは 2 と 5 の組合せで作れない個数について、答えを正しく計算することができないので、
  ちょうど n 個ではなく、"n 個以上" のりんごを買うのに必要な金額の最小値を求めることを考える。

• dp を添字が大きい方から dp[i] = Math.min(dp[i], dp[i+1]) のように書き換えて、i 個ちょうど買う時と i 個以上買う時のどちらが最安か比較していけば、
  dp[n] が n 個以上のりんごを買うのに必要な金額の最小値となる。

※補足として、

• n+5 まで計算するのは、n個以上買ったときの場合をカバーするため、
• n個以上のりんごを買うのに必要な金額の最小値を求めるときに、逆順に更新するのは、dp[i+1] がすでに「以上」に更新済みである必要性があるため。

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