치춘짱베리굿나이스
[백준] 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하여 한번에 출력해준다
'Javascript + Typescript > 자바스크립트로 알고리즘풀기' 카테고리의 다른 글
[백준] 24082 (0) | 2022.06.12 |
---|---|
[백준] 15964 (0) | 2022.06.12 |
[백준] 2530 (0) | 2022.06.12 |
[백준] 11055 (0) | 2022.06.12 |
[백준] 15894 (0) | 2022.06.12 |
Comments