[백준/JS] 15989 1, 2, 3 더하기 4

참고블로그

📝 문제

일단 분류를 먼저 봅시다.

다이나믹 프로그래밍 입니다...!!

이 문제에서는 1,2,3 을 더해서 숫자를 표현해줍니다!
근데 중복을 허용해주지 않습니다.
이 말은 1+2 와 2+1이 동일하다고 보는겁니다.

중복을 허용해주는 경우

이 문제 가 중복을 허용해주는 경우입니다.

이 경우에는

d[n] = d[n-1] + d[n-2] + d[n-3] 의 식이 생깁니다.

😅 중복을 허용해주지 않습니다..

이 문제는 중복을 허용해주지 않기 때문에 위 그림 처럼 중복되는 경우가 제외되게 됩니다.

중복을 제외하고서 봤을때

3을 만드는 경우는 마지막 숫자가 1인 경우까지 포함
2를 만드는 경우는 마지막 숫자가 2인 경우까지 포함
1을 만드는 경우는 전체가 포함

따라서 이차원 배열로 마지막 숫자가 1,2,3인 경우에 대한 값을 저장해주면 됩니다.

다른 예시를 통해서 다시 이해해보면

d[5] =
d[4][1] +
d[3][1] + d[3][2] +
d[2][1] + d[2][2] + d[2][3] 인 것을 확인할 수 있습니다.

고로 식은

d[n] =
d[n-1][1] +
d[n-2][1] + d[n-2][2] +
d[n-3][1] + d[n-3][2] + d[n-3][3] 이 됩니다.

✏️ 결과 코드

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

let tc = Number(input.shift());

let dp = Array.from(Array(10001), () => Array(4).fill(0));

dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 1;
dp[3][1] = 1;
dp[3][2] = 1;
dp[3][3] = 1;

for (let i = 4; i <= 10000; i++) {
  dp[i][1] = dp[i - 1][1];
  dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
  dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
}

for (let t = 0; t < tc; t++) {
  let n = Number(input.shift());

  console.log(dp[n][1] + dp[n][2] + dp[n][3]);
}