[Baekjoon Online Judge] 9461번: 파도반 수열

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)을 출력한다.

---

우선 제공된 수열을 가지고 일정한 규칙을 찾아보았다.

 

P(1)	P(2)	P(3)	P(4)	P(5)	P(6)	P(7)	P(8)	P(9)	P(10)
1	1	1	2	2	3	4	5	7	9

 

처음 규칙을 찾았을 때 P(n) = P(n - 2) + P(n - 3) 이라고 가정하였다. 언뜻보면 맞는 것 같지만 그림을 살펴보면, P(10)은

P(5) + P(9)의 합인 2 + 7 = 9인것을 알 수 있다. 삼각형의 크기가 커질수록 일정한 규칙을 가지는 것을 확인 할 수 있었다.

 

 

즉, P(n) = P(n - 1) + P(n - 5)라는 공식이 나오게 된다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Baekjoon9461 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(bufferedReader.readLine()); // 1 ~ 100

        long[] dp = new long[101];

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

        for (int i = 5; i < dp.length; i++)
            dp[i] = dp[i - 1] + dp[i - 5];

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(bufferedReader.readLine());
            bufferedWriter.write(dp[n] + "\n");
        }

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}