[백준 9461번] 파도반 수열

문제 링크: 9461번 파도반 수열

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

 

나열을 통해 다음과 같은 점화식을 이끌어낼 수 있다.

 

a[n] = a[n-1] + a[n-5]

 

참고로, 이는 정삼각형의 한 각의 크기가 60도라는 것과 관련이 있다고 한다. 그리고 처음에 long형을 사용하지 않아서 틀렸다. 생각보다 숫자가 빨리 커지는데, 대략적인 숫자의 크기에 대해서도 충분히 고려해야 할 것이다.

 

import java.util.Scanner;

public class Main {
    public static long longest(int n) {
        long[] arr = new long[101];
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        arr[4] = 2;
        arr[5] = 2;
        for (int i = 6; i <= n; i++)
            arr[i] = arr[i-1] + arr[i-5];
        return arr[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt();
        for (int c = 0; c < cases; c++) {
            int n = sc.nextInt();
            System.out.println(longest(n));
        }
        sc.close();
    }
}