[백준] 15990번 1, 2, 3 더하기 5 - JavaScript(NodeJS)

문제

15990번: 1, 2, 3 더하기 5

 

풀이

숫자 n을 1,2,3의 합으로 표현하는 경우의 수를 구한다.

1,2,3을 여러 번 사용할 수 있으나, 연속되게 사용하면 안된다.

숫자 4를 표현할 때 1+1+2, 2+2 와 같이 연속되게 같은 숫자를 사용할 수 없다.

 

이 문제는 dp 유형으로 점화식을 구해야 한다.

 

우선 1부터 시작해보자.

 

n=1 일 때, 1
n=2 일 때, 2
n=3 일 때, 1+2, 2+1, 3
n=4 일 때, 1+2+1, 1+3, 3+1
n=5 일 때, 1+3+1, 2+1+2, 3+2, 2+3

 

사실 이렇게만 보면 점화식을 파악하기 어려울 수 있다.

 

 

마지막 숫자를 기준으로 생각해본다.

 

n이 100일 때, 마지막 숫자가 1일 경우는
... +2 +1
... +3 +1
2가지이다.

 

마지막 숫자 앞에 더해진 숫자가 2이거나 3이어야 한다.

즉 n=99일 때 마지막에 더해진 숫자가 2이거나 3인 경우의 수를 더해주면, n=100일 때 마지막 숫자가 1인 경우의 수가 된다.

 

마찬가지로 마지막 숫자가 2일 경우 역시
... +1 +2
... +3 +2
2가지이다.

 

마지막에 2를 더해야 하므로, n=98일 때 마지막 숫자가 1이거나 3인 경우의 수를 더하면 된다.

 

 

그러므로 2차원 배열을 이용해 1~N 까지 마지막 숫자가 1,2,3이 들어가는 경우의 수를 구해야 한다.

 

숫자 N의 경우의 수를 구할 때, 마지막 숫자가 1,2,3인 경우의 수를 모두 더해주면 된다.

 

코드

function sol(input) {
  const MOD = 1000000009;
  const SIZE = 100000;
  const dp = Array.from({ length: SIZE + 1 }, () => new Array(4).fill(0));

  // for 문에서 i-1 ~ i-3이 무난하게 동작하기 위해 n=1,2,3 값을 채운다.
  dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
  for (let i = 4; i < SIZE + 1; i++) {
    dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
    dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
    dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
  }

  let answer = "";
  input.slice(1).map((n) => {
    n = +n;
    answer += `${(dp[n][1] + dp[n][2] + dp[n][3]) % MOD}\n`;
  });
  return answer;
}

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });