BOJ - 파도반 수열

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

9461번: 파도반 수열

 

• 주어진 조건에 따라 점화식을 세우고 메모리제이션으로 최적화하면 통과 할수 있다!
• 값의 범위가 int형을 초과하기때문에 long으로 변경한다.

 

import java.util.Arrays;
import java.util.Scanner;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static long[] memo = new long[100 + 2];

    public static void main(String[] args) throws Exception {
        int T = scanner.nextInt();

        Arrays.fill(memo, 0);
        memo[1] = 1;
        memo[2] = 1;
        memo[3] = 1;
        memo[4] = 2;
        memo[5] = 2;

        while (T-- > 0) {
            int N = scanner.nextInt();
            System.out.println(w(N));
        }
    }

    private static long w(int N) {
        if (N == 1) return 1;
        if (N == 2) return 1;
        if (N == 3) return 1;
        if (N == 4) return 2;
        if (N == 5) return 2;

        if (memo[N] != 0) {
            return memo[N];
        }

        memo[N] = w(N - 1) + w(N - 5);

        return memo[N];
    }
}