[백준] 9461

파도반 수열

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

풀이

const padovan = () => {
  let [t, ...input] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map(Number);
  const max = Math.max(...input);
  let arr = [];
  if (max < 6) {
    for (let i of input) {
      if (i < 4) arr.push(1);
      else if (i < 6) arr.push(2);
    }
    console.log(arr.join("\n"));
    return;
  }
  let dp = Array.from({ length: max + 1 }, (v) => 0);
  (dp[1] = 1), (dp[2] = 1), (dp[3] = 1), (dp[4] = 2), (dp[5] = 2);
  for (let i = 6; i <= max; i++) {
    dp[i] = dp[i - 5] + dp[i - 1];
  }
  for (let i of input) arr.push(dp[i]);
  console.log(arr.join("\n"));
};

padovan();

반성회

• 입력으로 들어온 테스트케이스 중 가장 큰 케이스까지 dp 진행
• 만약 입력으로 들어온 테스트케이스가 전부 6 미만일 경우
  • dp[1], dp[2], dp[3], dp[4], dp[5] 를 초기화해줘야 하는데 오류가 날 수 있으므로 예외처리를 해준다
  • 테스트케이스가 1, 2, 3일 경우 1을, 4, 5일 경우 2를 출력한다
• dp배열의 앞 5개는 보편적인 규칙을 따르지 않으므로 직접 초기화해준다
• dp 규칙은 dp[N] = dp[N - 1] + dp[N - 5]
• 따라서 dp 배열을 최대값까지 채워준 후 arr에 하나씩 push하여 한번에 출력해준다