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

문제

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

풀이

핵심 풀이

const arr = [0, ...input().split(" ").map(Number)];

for (let i = 1; i <= N; i++) {
  for (let j = 0; j <= Math.floor(i / 2); j++) {
    arr[i] = Math.min(arr[i], arr[j] + arr[i - j]);
  }
}

• 이 문제에서는 카드의 개수가 1개일 때, 2개일 때, ... 지불 가능한 비용의 최솟값을 매번 갱신해주고 그 값을 다음 계산에서 바로 활용하는 게 핵심이다.
• dp[N] = N개의 카드로 지불해야 하는 금액의 최솟값 으로 정의하면, 문제에서 주어진 카드의 금액(arr[N])보다 이 dp[N]의 값이 작아질 수 있다. 따라서 갱신할 때의 초기값으로 arr[N]을 활용하는 것이 아닌 dp[N]을 활용해야 하며, 이는 arr[N]과 dp[N]의 분리가 불필요함을 의미하므로 dp 배열을 굳이 사용하기보다 arr 배열의 값을 갱신해주면 된다.

틀렸던 이유

• 복잡하게 생각해서, 처음에는 카드 개수를 직접 곱셈으로 계산해야 한다고 접근했다. 이렇게 풀면 카드 개수가 바뀔때마다 최솟값이 달라질 수 있으므로 계산해줘야 하는 경우의 수가 복잡해진다는 걸 알고, 다시 생각해보게 됐다.
• 틀렸던 포인트 1: 값을 갱신할 때, 이전에 최소값을 구했다면 그 최솟값을 활용해서 다시 구해야 한다!
• 틀렸던 포인트 2: 배열의 반복문을 돌며 값을 갱신할 때, (i/2) 번째 까지만 돌면 아직 정의되지 않은 값에 접근하는 걸 막을 수 있다!

전체 풀이

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

const solution = () => {
  const N = +input();
  const arr = [0, ...input().split(" ").map(Number)];

  for (let i = 1; i <= N; i++) {
    for (let j = 0; j <= Math.floor(i / 2); j++) {
      arr[i] = Math.min(arr[i], arr[j] + arr[i - j]);
    }
  }
  console.log(arr[N]);
};

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

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