백준 9461) 파도반 수열 Java 자바

문제

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

 

정답

dp를 이용해 풀이하였고, 누적되는 규칙성을 파악한 뒤 1<= N <= 100 의 범위에 따라 미리 dp 배열의 정의해 주었다.

이 후 입력 값에 맞는 dp배열 값을 출력해주면 된다.

 

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

public class Main {

    static long[] dp = new long[101];
    static int N;

    public static void pre(){

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

        for (int i = 4; i < 101; i ++){
            dp[i] = dp[i-2] + dp[i-3];
        }
    }

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

        N = Integer.parseInt(br.readLine());
        pre();

        for (int i = 0 ; i < N ; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}