[백준] 9095: 1, 2, 3 더하기 - JS (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

  접근 방식

 

규칙을 먼저 찾아보자.

 

1의 경우: 1

2의 경우: 2

3의 경우: 4

4의 경우: 7

5의 경우: 13

6의 경우: 24

 

4의 경우를 살펴보면 앞에 3개를 더한 값이다. 5의 경우도 직전 3개를 더한 값이다.

만약 저 숫자들이 dp 배열에 있다고 한다면, dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이 된다는 의미이다.

 

반복문의 조건식은 i <= 10으로 해주고, i는 4부터 시작한다. 

3까지는 직접 넣어준다.

const dp = [0, 1, 2, 4];

 

 

 

  풀이

 

 

const fs = require('fs');

let [n, ...input] = fs.readFileSync('dev/stdin').toString().trim().split('\n');
input = input.map(Number);


const dp = [0, 1, 2, 4];

let i = dp.length;

while(i <= 10){
	if(!dp[i]){
		dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
	};
  i++;
}

input.forEach((v) => {
  console.log(dp[v]);
});