백준 15988번 1, 2, 3 더하기 node js

문제

https://www.acmicpc.net/problem/15988

 

 

풀이

 

n의 경우의 수를 구하기 위해 n보다 작은 값들의 경우를 저장해놓고 n의 경우의 수를 구할 수 있다. -> dp 문제

 

1. 반복되는 패턴에서 점화식을 세운다.

2. 점화식을 구현

 

5까지 경우의 수를 나열해보면 반복되는 패턴을 찾았고

dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 점화식을 찾을 수 있다.

 

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n').map(Number);

const T = input.shift();

const dp = new Array(T+1);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;

const num = Math.max(...input);

for(let i=4; i<=num; i++) {
    dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 1000000009;
    // dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}

input.map((v, i) => console.log(dp[input[i]]));
// input.map((v, i) => console.log(dp[input[i]] % 1000000009)); -> 이거는 오답처리됨.. 이유가..? 예외케이스가 있나?