백준|11727번|2xN 타일링 2

문제설명
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제입니다.

작동 순서
순서대로 구해보면
n=1일 때 1
n=2일 때 3
n=3일 때 5
n=4일 때 11
n=5일 때 21...
으로 dp[n]=dp[n-1]+dp[n-2]*2인 것을 알수 있습니다.
그리고 이 문제의 답을 출력할 때 10007로 나눈 나머지를 출력해야하므로 계산할 때 10007로 나눈 나머지를 입력해주면 됩니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 백준_11727번_2xn타일링2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[] dp=new int[1001];
        dp[1]=1;
        dp[2]=3;
        dp[3]=5;
        for(int i=4;i<n+1;i++){
            dp[i]=(dp[i-2]*2+dp[i-1])%10007;
        }
        System.out.print(dp[n]);
    }
}