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

이 문제를 처음에 접할 때, 이차원 배열, 일차원 배열을 생각하면서 접근했다. 그런데 n = 1부터 n = 5까지 그림을 그리면서 하는데 규칙성이 보이게 됬다.  피보나치와 비슷한 규칙을 가지게 된다.

 

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(tile(N));
    }
    
    public static int tile(int n){
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(dp[n] != -1) return dp[n];
        
        dp[n] = (tile(n-1) + tile(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] = 1;
        dp[1] = 1;
        
        
        for(int i = 2; i <= N; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
            }
        
        
        System.out.print(dp[N]);
    }
}