BaekJoon_9461 (파도반 수열)

문제

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

9461번: 파도반 수열

문제 풀이

N은1 부터 차근차근히 그림을 그려나가 보면 점화식을 금방 발견할 수 있다.

N	1	2	3	4	5	6	7
정삼각형 변의 길이	1	1	1	2	2	3	4

점화식 : dp[n] = dp[i-1] + dp[i-5]

초기값 : dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2, dp[5] = 2

 

코드

const answer = ([...number]) => {

  const arr = number.map(data => Number(data))

  const order = arr[0];

  let dp = [];

  for (let index = 1; index <= order; index++) {
    dp = Array.from({ length: arr[index] + 1 }, () => 0);

    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;
    dp[5] = 2;

    for (let index = 6; index < dp.length; index++) {
      dp[index] = dp[index - 1] + dp[index - 5];
    }

    console.log(dp[arr[index]])
  }
};


const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    // console.log(input)
    answer(input);
    process.exit();
  });

// https://www.acmicpc.net/problem/9461
// 다이내믹 프로그래밍은 점화식을 찾아서 리스트화 하는게 핵심

 

코드는 깃헙에서도 확인 가능합니다 :)

https://github.com/duduchi/Algorithm/tree/main/Dynamic

GitHub - duduchi/Algorithm: 알고리즘 이론 및 구현 소스 정리 프로젝트 입니다.