[백준 9507] Generations of Tribbles

 

입력한 수  n 에 대하여 n번째 피보나치 수열을 구하면 된다.

점화식은 문제에 나와있는 식대로 하면되고 입력의 최대값이 t<69 이므로 long 타입으로 구해야 한다.

 

 

public static long dp[] = new long[68];
    
    public static long f(int n) {
        if(n < 2) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;
        if(dp[n] != -1) return dp[n];
        
        long result = f(n-1) + f(n-2) + f(n-3) + f(n-4);
        dp[n] = result;
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        
        for(int i=0; i<dp.length; i++)
            dp[i] = -1;
        
        while(t-->0) {
            int n = sc.nextInt();
            
            System.out.println(f(n));
        }
        
        sc.close();
}