[boj] 11052. 카드 구매하기 (node.js)

문제 요약

[boj] 11052. 카드 구매하기 (node.js)

풀이

• N개의 카드를 구매하려 한다. 배열에 순서대로 1장짜리 카드, 2장짜리 카드, ..., k장짜리 카드의 판매 가격 배열이 주어질 때,
• N개의 카드르 구매할 수 있는 가장 비싼 가격은?

내 풀이

• 동적 프로그래밍 문제
• dp[N] = N개의 카드를 구매할 수 있는 가장 비싼 금액
• X = 1에서 시작해서 dp[X]를 구한다. for X = 1; X <= N; X++
  • for 문 내부에서 점화식을 통해 해당 장수에서의 최댓값을 계산한다.
    • 금액 배열의 인덱스가 곧 카드의 장수를 의미하므로 1부터 시작하도록 index = i+1로 설정하고 점화식을 세울 수 있다.
      • 예시: dp[4장]
      • = Math.max(dp[3장] + dp[1장] / dp[2장] + dp[2장] / dp[4장] + dp[0장])
    • 즉, for (let i = 0; i <N; i++) 을 돌며
    • let max = Math.max(dp[index] + dp[X - index], max) 를 갱신한다.
  • 계산이 완료되면 dp[X] 에 max 값을 대입한다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = input();
  const price = input().split(" ").map(Number);
  let dp = new Array(N + 1).fill(0);
  price.forEach((elem, idx) => (dp[idx + 1] = elem));
  dynamic();
  console.log(dp[N]);

  function dynamic() {
    for (let X = 1; X <= N; X++) {
      let max = dp[X];
      for (let i = 0; i < N; i++) {
        let index = i + 1;
        if (X - index <= 0) continue;
        max = Math.max(dp[index] + dp[X - index], max);
      }
      dp[X] = max;
    }
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});