[백준 알고리즘] Node.js 9461. 파도반 수열

1. 문제

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

9461번: 파도반 수열

 

2. 풀이

- DP를 이용한 문제이기 때문에 점화식을 찾아야한다.

p(1) = 1;
p(2) = 1;
p(3) = 1;
p(4) = 2 = p(1) + p(2)
p(5) = 2 = p(3) + p(2)
p(6) = 3 = p(5) + p(1)
p(7) = 4 = p(6) + p(2)
p(8) = 5 = p(7) + p(3)
p(9) = 7 = p(8) + p(4)
p(10) = 9 = p(9) + p(5)
p(11) = 12 = p(10) + p(6)
p(12) = 16 = p(11) + p(7)
p(13) = 21 = p(12) + p(8)

- 이런 방식으로 진행된다고 생각하고 코드를 작성했다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);
const t = inputs.shift();
const dp = [];
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
dp[4] = 2;
dp[5] = 2;

let answer = "";
for(let i = 0; i < t; i++){
  for(let j = 6; j <= inputs[i]; j++){
    dp[j] = dp[j-1] + dp[j-5];
  }

  answer += `${dp[inputs[i]]}\n`;
}

console.log(answer)

 

3. 다른 사람의 풀이

-  n = (n-3) + (n-2) 으로 진행된다고 한다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);
const t = inputs.shift();
const dp = [];
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;

let answer = "";
for(let i = 0; i < t; i++){
  for(let j = 4; j <= inputs[i]; j++){
    dp[j] = dp[j-3] + dp[j-2];
  }

  answer += `${dp[inputs[i]]}\n`;
}

console.log(answer)