[백준] 9461. 파도반 수열 (자바스크립트/javascript/js/node.js/동적계획법/다이나믹 프로그래밍/동적 프로그래밍)

 

 

 

문제를 풀기 위한 아이디어

동적 프로그래밍 유형이 다들 그러듯이 점화식만 잘 세우면 된다.

점화식은 다른 분들의 코드를 보니까 여러 점화식이 나올 수 있는데

나는 그림을 보고 바로 유추할 수 있는 점화식을 사용했다.

P(1) = 1

P(2) = 1

P(3) = 1

P(4) = 2

P(5) = 2

P(6) = 3

P(7) = 4

P(8) = 5

까지는 값을 미리 넣어놓고, P(9)부터는 P(N) = P(N-5) + P(N-1)을 사용했다.

사실 P(1)~P(3)까지만 넣어놓고 P(4)부터 P(N)  = P(N-2) + P(N-3)을 쓰는 것이 더 좋은 방법인 것 같긴 하다.

하지만 나는 그림을 보고 예를 들어 P(9) = P(4) + P(8)의 합이라고 딱 그림에서 보기 쉬웠기 때문에 이렇게 점화식을 세웠다.

 

 

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let input = fs
  .readFileSync("예제.txt")
  .toString()
  .split("\n")
  .map((element) => Number(element));
const T = input[0];
input.shift();
const answer = [];
const memo = new Array(101).fill(0);
memo[1] = 1;
memo[2] = 1;
memo[3] = 1;
memo[4] = memo[1] + memo[3];
memo[5] = memo[4];
memo[6] = memo[3] + memo[5];
memo[7] = memo[2] + memo[6];
memo[8] = memo[1] + memo[7];

for (let i = 0; i < T; i++) {
  if (input[i] >= 9) {
    for (let j = 9; j <= input[i]; j++) {
      memo[j] = memo[j - 5] + memo[j - 1];
    }
    answer.push(memo[input[i]]);
  } else {
    answer.push(memo[input[i]]);
  }
}