# BOJ09461 파도반 수열
https://www.acmicpc.net/problem/9461 (opens new window)
삼각형이 나선 모양으로 놓여져 있다. 첫 삼각현은 정삼각형으로 변의 길이가 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.
p(1) = 1
p(2) = 1
p(3) = 1
p(4) = 2
p(5) = 2
p(6) = 3
p(7) = 4
p(8) = 5
p(9) = 7
p(10) = 9
...
N이 주어졌을 때, P(N)을 구한다.
# 점화식
위의 숫자를 잘 살펴보면 나선에서 가장 긴 변 k는 이전 삼각형과 5번째 이전 삼각형의 변의 합이 새롭게 그릴 삼각형의 변이 된다. 이것은 n의 크기가 6이상 일 때 부터 적용이 가능하다.
n = 1 일 때, p(n) = 1
n = 2 일 때, p(n) = 1
n = 3 일 때, p(n) = 1
n = 4 일 때, p(n) = 2
n = 5 일 때, p(n) = 2
n >= 6 일 때, p(n) = p(n - 1) + p(n - 5);
# 제출 코드
아래는 최종 제출 코드이다.
import java.util.Scanner;
public class BOJ9461 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
long[] dp = new long[101];
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
dp[4] = 2;
dp[5] = 2;
for (int i = 6; i <= 100; i++) {
dp[i] = dp[i - 1] + dp[i - 5];
}
while (t-- > 0) {
int n = scanner.nextInt();
System.out.println(dp[n]);
}
}
}