99클럽 코테 스터디 29일차 TIL - 백준 9461 파도반 수열

Input

1. T: 테스트케이스
2. ~T. N(1~100)

Output

1. P(N)

Solve

일단 규칙을 살펴보자

a b c d e
1 1 1 2 2 3 4 5 7 9 12

수학은 잘 모르지만, 잘 보면 d 부터 규칙이 생긴다.
a+b=d 해당 규칙이 나오는데, index로 표현하면 seq[0] + seq[1] = seq[3]이다. 해당 규칙을 바탕으로 100까지 배열에 저장해두고 테스트케이스를 처리하면 된다.

처음에 int배열로 돌렸다가 실패했다.
가장먼저 고려하지 않았던 수의 크기를 생각해보았고, 아무리 규칙을 뚫어져라 봐도 수가 얼마나 커질지는 예상을 못하겠어서 그냥 long으로 바꾸니까 잘 됐다.

Code

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

public class BOJ_9461_파도반수열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        long[] sequence = new long[100];
        sequence[0] = sequence[1] = sequence[2] = 1;
        for (int i = 3; i < 100; i++) {
            sequence[i] = sequence[i-3] + sequence[i-2];
        }

        while(T-->0) {
            int N = Integer.parseInt(br.readLine());
            if (N < 4) sb.append("1").append("\n");
            else sb.append(sequence[N-1]).append("\n");
        }

        System.out.println(sb);

    }
}