[백준 Java] 9461 파도반 수열

문제 링크

https://www.acmicpc.net/problem/9461

풀이

수열의 규칙을 찾는다.

1 1 1 2 2 3 4 5 6 7 9 12를 봤을 때, 1 1 1 2 2 까지는 규칙을 찾기 어렵지만, 3부터는 n-1과 n-5의 값이 합쳐진게 답이 된다.

문제에서 P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 라고 되어있기 때문에 각 단계별로 배열을 만든 다음 값을 사용한다.

N이 100까지 들어오기 때문에 배열의 크기를 100으로 잡고, 값이 int 자료형의 범위를 벗어나기 때문에 long을 사용한다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //int 자료형을 사용하면 오버플로우 발생
        long[] dp = new long[101];
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;
        dp[5] = 2;
        //이후 값은 dp[n-1] + dp[n-5] 값을 따름
        for (int i = 6; i < dp.length; i++) {
            dp[i] = dp[i-1] + dp[i-5];
        }

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(T-- > 0){
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N]).append("\n");
        }
        System.out.println(sb);
    }
}