[백준] 11727 2*N 타일링 2

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

 

내 풀이

 

2*1 , 1*2 , 2*2 타일로 채우는 방법의 수를 찾는 것 고로

2*n 블럭 만드는 경우의 수를 2* n-2  블럭에서 만드는 경우와 2* n-1 블럭에서 만드는 경우를 고려하여 dp를 만들었다.

그것을 수식으로 

DP[n] = DP[n-1] + 2 * DP[n-2] 로 만들 수 있었다.

 

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	
	//static StringBuilder output = new StringBuilder();
	
	public static void main(String arg[]) throws IOException {
		Scanner sc= new Scanner(System.in);
		int input= sc.nextInt();
		long[] DP=new long[1001];
		DP[1]=1;
		DP[2]=3;
		
		for(int i=3;i<=input;i++) {
			DP[i]=(DP[i-1]+2*DP[i-2])%10007;
		}
		
		System.out.print(DP[input]%10007);
		
	}
	
}