자바(백준) 11726 2*N 타일링 2

 

 

 

Top down 방식

import java.io.IOException;
import java.io.BufferedReader;    
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main { 
    
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        
        dp = new int[N+1];
        Arrays.fill(dp, -1);
        
        
        System.out.print(tileTwo(N));
    }
    
    public static int tileTwo(int n) {
        if(n == 0 || n == 1) return 1;
        if(dp[n] != -1 ) return dp[n];
        
        dp[n] = (tileTwo(n-1) + 2 * tileTwo(n-2)) % 10007;
        return dp[n];
    }
}
 

Bottom up 방식

 

import java.io.IOException;
import java.io.BufferedReader;    
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main { 
    
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        
        dp = new int[N+1];
        
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= N; i++) {
            dp[i] = (dp[i-1] + 2 * dp[i-2]) % 10007;
        }
        
        System.out.print(dp[N]);
    }
}