알고리즘106 :: BOJ_11726_2XN타일링

package backjun;
 
import java.util.*;
public class BOJ_11726_2n타일링 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+2];
        
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++) {
            dp[i] = (dp[i-1]+dp[i-2])%10007; 
        }
        System.out.println(dp[n]);
    }
}
 

 

dp[n+1] 라고 하면 n이 1이라면 dp[2] 가 2 가 된다면 dp의 크기가 2인데 접근이 2가 되서 인덱스가 어레이를 초과하게 됩니다. 

 

2) 탑다운

import java.util.*;
public class Main {
    static int[] dp = new int[1001];
    static int fibo(int n) {
        if(n==0 || n==1)
            return 1;
        if(dp[n]>0)
            return dp[n];
        dp[n] = fibo(n-1)+fibo(n-2);
        dp[n] %= 10007;
        
        return dp[n];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fibo(n));
    }
}