[JAVA] 백준 11727번 【2×n 타일링 2】

---

11726번 문제와 굉장히 유사하다.

 

[JAVA] 백준 11726번 【2×n 타일링】

11726 번을 먼저 이해하는 것이 좋다.

 

차이점이라고 한다면, 2*2 사각형도 사용하여 채우기 때문에, 

 

2*3 사각형 경우의 수에서, 2*1 사각형 경우의 수가 2번 있는 것과 같은 이치가 된다.

 

즉 Dp[n] = Dp[n-1] +2*Dp[n-2] 식으로 점화식을 구성하면 된다!

 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int [] Dp = new int[n+1];
		Dp[0]=1; // 2*1 사각형 경우의 수
		Dp[1]=3; // 2*2 사각형 경우의 수
		for(int i=2;i<n;i++) {
			Dp[i]=(Dp[i-1]+Dp[i-2]*2)%10007; 
		}
		System.out.println(Dp[n-1]); //2*n 사각형 경우의 수

	}
}