백준알고리즘 9461번 파도반 수열

백준알고리즘

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

그림을 그려가며 하나하나 순서대로 계산해서 답을 구해보았더니

1,1,1,2,2,3,4,5,7,9,12,16,21,28 ... 

규칙을 찾아보았다 d[n] = d[n-1] + d[n-5];

처음 5가지의 값을 배열에 저장해놓고 그 이후의 값을 하나하나 구했더니 정답.

참고로 int형은 런타임 에러가 발생하였다. int의 범위를 초과하였다. 그래서 long로 변경하여 실행하니 정답.

public class Test {
    public static int[] memoArray = { 0, 1, 1, 1, 2, 2 };
    public static long[] calArray;
    public static int count;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in); 
        count = Integer.parseInt(scan.nextLine().trim());
        
        for(int i = 0; i < count; i++) {
            int value = Integer.parseInt(scan.nextLine().trim());
            calArray = new long[100+2];
            
            for(int j = 0; j < memoArray.length; j++) {
                calArray[j] = memoArray[j];
            }
        
            calculate(value);
        }
    }
    
    public static void calculate(int value) {
        if(value <= 5) {
            System.out.println(calArray[value]);
            return ;
        }
        
        for(int i = 6; i <= value; i++) {
            calArray[i] = calArray[i-1] + calArray[i-5];
        }
        
        System.out.println(calArray[value]);
    }
}