[백준 2193] 이친수

 

 

n자리 이친수의 개수를 세어보면 피보나치 수열이란 것을 알 수 있다.

 

 

 

1. n의 범위가 90 까지이므로 자료형을 long 으로 선언해야 한다.

 

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