[BOJ] 11727. 2xn 타일링2

DP를 사용하는 전형적인 문제이다.

1X2, 2X2, 2X1 세가지 블럭이 있으므로 다음과 같은 점화식을 구할 수 있다.

dp[N]= (dp[N-1]에서 세로블럭 1개 더해서 만들기)
+ (dp[N-2]에서 가로블록 2개 더해서 만들기)
+ (dp[N-2]에서 정사각형 블록 1개 더해서 만들기)

위와 같은 점화식으로 쉽게 dp를 구할 수 있고, 조건에서 10007로 나눈 수를 구하라 했으므로 연산 결과마다 10007을 나누어 주었다.

package boj.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_11727_2xn타일링2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
 
        if(N==1) {
            System.out.println(1);
            return;
        }
        
        int[] dp=new int[N+1];
        
        dp[1]=1;
        dp[2]=3;
        
        for(int i=3;i<=N;i++) {
            dp[i]=dp[i-1]+ dp[i-2]+ dp[i-2];
            dp[i]=dp[i]%10007;
        }
        
        System.out.println(dp[N]);
    }
}