[백준] 11727번: 2xn 타일링 2

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

11727번: 2×n 타일링 2

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int[] dp = new int[1001];
		dp[1] = 1;
		dp[2] = 3;
		for(int i=3; i<1001; i++) 
			dp[i] = (dp[i-1] + (2*dp[i-2])) % 10007;
		
		System.out.println(dp[n]);
		scan.close();
	}

}

풀이

2xn타일링 

위 문제는 1x2 , 2x1 타일로 채우지만 이 문제는 2x1 , 2x2 타일로 채우는 방법의 수이다.

 

2x1이라고 해서 길쭉한 세로 직사각형만 생각했는데, 이 세로를 눕히면 가로 직사각형도 가능하다.

마지막 네모를 2X1 직사각형 하나로 놓는 경우 -> dp[n-1]

마지막 네모를 1X2 직사각형 두개로 놓는 경우 -> dp[n-2]

 

그리고 추가적으로 마지막으로 네모를 2x2 직사각형 한개로 놓는경우 -> dp[n-2] 의 방법이 있다.

따라서 최종 점화식은 아래와 같다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-2]

dp[n] = dp[n-1] + (2 * dp[n-2])