[백준] 15990번 1, 2, 3 더하기 5

풀이

점화식을 만드는 게 힘들어서 결국 구글링을 했다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n').map(x=>+x);

const n = Number(input.shift());
const max = Math.max(...input);
const num = 1000000009;
let answer = '';

const dp = Array.from(Array(max+1), () => []);
dp[0] = [0];
dp[1] = [0,1,0,0];
dp[2] = [0,0,1,0];
dp[3] = [0,1,1,1];

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

for(let i=0; i < n; i++) {
    answer += dp[input[i]].reduce((a,b) => a+b, 0) % num + '\n';
}

console.log(answer);

• 9095번 문제와 다르게 비슷하지만 연속된 숫자를 사용하면 안된다는 조건이 있다.

• 그래서 1차원 배열로 했던 9095번 문제와 다르게 dp배열을 2차원으로 만든다.

• dp[n][1]은 마지막에 1을 더하는데, 이전에 1을 사용한 곳에는 더하면 안되니 직전(dp[n-1])의 마지막이 2와 3인 것을 더해준다.

• dp[n][2]는 마지막에 2을 더하는데, 이전에 2을 사용한 곳에는 더하면 안되니

• 전전(dp[n-2])의 마지막이 1과 3인 것을 더해준다.

• dp[n][3]은 마지막에 3을 더하는데, 이전에 3을 사용한 곳에는 더하면 안되니
  전전전(dp[n-3])의 마지막이 1과 2인 것을 더해준다.

그러면 점화식은 이렇게 세워진다.
dp[n][1] = dp[n-1][2] + dp[n-1][3]
dp[n][2] = dp[n-2][1] + dp[n-2][3]
dp[n][3] = dp[n-3][1] + dp[n-3][2]

dp[n] = dp[n][1] + dp[n][2] + dp[n][3]

처음에 갑자기 이차원배열이 나와서 약간 이해가 안될뻔 했는데 이차원 배열로도 생각하는 연습을 해야겠다.

설명 참고 블로그