파도반 수열

문제

언어

  • JavaScript

문제 풀이 step 1

  • 변의 길이가 1일때부터 그리면서 정삼각형을 키우다보면 어느 순간부터 이전의 정삼각형들의 변이 합해져서 새로운 정삼각형의 변이 결정된다는 것을 알 수 있습니다.
  • 작은 문제의 해답으로부터 큰 문제의 해답을 구할 수 있으므로 다이나믹 프로그래밍 기법으로 해결합니다.
  • dp[n] = n번째 정삼각형의 변의 길이
    • 한 단계 전의 삼각형의 변의 길이와 5단계 전의 삼각형의 변의 길이의 합으로 n번째 정삼각형의 변의 길이가 결정됩니다.
    • dp[n] = dp[n-1] + dp[n-5]

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	let T = parseInt(input[0]);
	const arr = input.slice(1, T + 1).map(Number);

	const dp = [1, 1, 1, 2, 2];
	for (let i = 5; i < 100; i++) {
		dp[i] = dp[i - 1] + dp[i - 5];
	}

	let res = "";
	let index = 1;
	while (T-- > 0) {
		res += `${dp[input[index++] - 1]}\n`;
	}

	return res;
};

console.log(solution(input));