[백준] 9095 - 1,2,3 더하기 (Javascript / node)

문제

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

9095번: 1, 2, 3 더하기

풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const T = Number(input[0]);

const dp = [1,2,4]
const getCount = (num) => {
  for(let i =0; i<num;i++){
    if(dp[i]) continue;
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
  }
  return dp[num-1]
}
for(let i =1; i<=T; i++){
  console.log(getCount(Number(input[i])));
}

 

일정한 규칙이 있는 DP문제이다. 

• 1일때는 1가지 밖에 없으니 dp[0] = 1
• 2일때는 1+1, 2 총 두가지로  dp[1] = 2
• 3일때는 1+1+1, 1+2, 2+1, 3 으로 총 네가지로 dp[2] = 4

어느정도 규칙이 보인다

• 4일때는 1+1+1+1 , 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 일곱가지로 dp[3] = 7
• 보이는 교칙은 구하는 숫자의 가짓수는 이전 숫자들의 가짓수들 합과 같다.

점화식을 도출해 보면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 이 나온다.