[백준] - 15989 1, 2, 3 더하기 4 (node.js)

문제링크

풀이

dp 문제다. 솔직히 말하면 제출하고 "이게되네.." 싶었다.... ㅋㅎㅋㅎㅋㅎㅋ

먼저 1로만 더해서(1+1+1+...+1) 만드는 경우를 고려해 저장할 dp 배열을 1로 초기화했다. i-2에 저장된 값에서 2를 더하고, i-3에 저장된 값에서 3을 더하면 i가 된다. 그래서 dp[i] += dp[i - 2] + dp[i - 3]가 되는데, 여기서 i-2와 i-3에서 중복되는 것이 있을 것이므로 그걸 빼주는 방식으로 구현했다. 이를 통해 구한 점화식은 dp[i] += dp[i - 2] + dp[i - 3] - dp[i - 5] 과 같다. n이 7일 때를 예로 들어 그려보면 아래와 같다.

코드

// 1, 2, 3 더하기 4

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const arr = fs.readFileSync(filePath).toString().trim().split("\n");

const t = Number(arr[0]);
let dp = new Array(10001).fill(1); // 1로만 만드는 경우

dp[2] = 2;
dp[3] = 3;
dp[4] = 4;

for (let i = 1; i <= t; i++) {
  const n = Number(arr[i]);
  for (let i = 5; i <= n; i++) {
    if (dp[i] === 1) {
      dp[i] += dp[i - 2] + dp[i - 3] - dp[i - 5];
    }
  }
  console.log(dp[n]);
}