[Java] BOJ 9461 파도반 수열

문제 

문제 링크 https://www.acmicpc.net/problem/9461

• 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다.
• 첫 삼각형은 정삼각형으로 변의 길이는 1이다.
• 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.
• 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
• N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
• 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

  

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

아이디어

• 파도반 수열의 값을 저장하는 배열을 N + 1 크기로 생성한다.
• 1번째, 2번째, 3번째 파도반 수열을 모두 1이므로 배열의 1, 2, 3번째 값을 1로 초기화해준다.
• 그리고 i번째 파도반 수열의 값은 i - 2번째 파도반 수열의 값과 i - 3번째 파도반 수열의 값을 더한 값이므로 4부터 N까지 반복문을 돌면서 i번째 파도반 수열의 값을 계산한다.

겪은 시행착오

• X

규칙 찾는 문제 재밌당 ㅎㅎ

코드

import java.util.*;
import java.io.*;

public class BOJ9461 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 테스트 케이스 개수
        int T = Integer.parseInt(br.readLine());

        for(int test = 0; test < T; test++){
            int N = Integer.parseInt(br.readLine());

            // 파도반 수열을 저장할 배열
            long tri[] = new long[N + 1];

            // 파도반 수열의 1번부터 3번까지는 모두 값이 1이기 때문에
            // 1, 2, 3번째 배열을 1로 초기화
            tri[1] = 1;

            if(N > 1){
                tri[2] = 1;
            }

            if(N > 2){
                tri[3] = 1;
            }

            // 4부터 N까지 반복
            for(int i = 4; i <= N; i++){
                // i번째 파도반 수열은 i-2번째와 i-3번째 수열 값을 합한 값
                tri[i] = tri[i - 2] + tri[i - 3];
            }

            sb.append(tri[N] + "\n");
        }
        System.out.println(sb);
    }
}