[BOJ] #DP - 11727번 2 x n 타일링2 (JAVA)

문제 출처 : https://www.acmicpc.net/problem/11727

 

2 x 1 과 2 x 2 을 기본적으로 왼쪽 그림과 같이 타일링 할 수 있다.

이를 T( 1 )과 T( 2 )라고 하겠다.

T( 3 )은 T( 2 ) 오른쪽에 2x1 타일을 더한 것과 같다. 

또한, T( 1 )에 2x2 타일과 2x1 타일 두개를 더한 것과 같다.

마찬가지로, T( 4 )는 T( 3 )에 2 x 1 타일을 더한 것

그리고 T( 2 )에 2 x 2 타일 또는 2 x 1 두개를 더한 것과 같다.

즉, T( n ) = T( n-1 ) + T( n-2 )*2 인 것을 알 수 있다.

아래는 전체 코드이다.

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

public class Main 
{	
    public static void main( String[] args ) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int result = solution(n);
		System.out.println(result);
	}
    
	public static int solution (int n){
        int[] resultArray = new int[n+1];
		for(int i = 1; i <= n; i ++){
			if(i == 1) resultArray[1] = 1;
			else if(i == 2) resultArray[2] = 3;
			else resultArray[i] = (resultArray[i-1] + resultArray[i-2] * 2) % 10007;
		}
		return resultArray[n];
	}
}