[백준] 파도반 수열 | 자바스크립트 JS | 다이나믹 프로그래밍 DP | S3

문제

 

위의 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

 

풀이 과정

다이나믹 프로그래밍 입문 문제인 백준의 피보나치 함수 문제와 유사하다. 규칙을 찾아 점화식을 작성하면 끝 ... 인데, 어딘가 요상한 규칙으로 풀었다 -.-

 

DP[N]은 DP[N-1] + DP[N-5]로군 🤤

 

제출 코드

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let TC, countTC;

const solution = (N) => {
  let DP = [0, 1, 1, 1, 2];
  for (let i = 5; i < N + 1; i++) {
    DP.push(DP[i - 1] + DP[i - 5]);
  }
  console.log(DP[N]);
};

readline
  .on("line", (line) => {
    if (!TC) {
      TC = +line;
      countTC = TC;
    } else {
      solution(+line);
      countTC--;
      if (!countTC) {
        readline.close();
      }
    }
  })
  .on("close", () => {
    process.exit();
  });

 

통과하긴 했으나, 다른 이들의 풀이를 참고하니 좀 더 적절한 규칙은 DP[N] = DP[N-2] + DP[N-3]인 듯 하다. 이 점화식을 사용했다면 첫 DP 배열 초기화도 길이가 5에서 3으로 줄었을텐데 ... 😅

 

문제 링크

9461번: 파도반 수열