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

---

 

먼저, 문제의 원리를 이해해야한다.

 

다이나믹 프로그래밍 문제로, Dp[n] 은 2*n 사각형의 경우의 수를 메모이제이션 해야한다.

 

2*1 사각형의 경우 1가지, 2*2 사각형의 경우 2가지가 나온다.

 

위 그림에 따라, 2*3 사각형을 생각해보면, 제일 오른쪽에 2*1 사각형을 추가하고나서 남은 2*2 사각형을 어떻게 채울지 고민해보면 되는데, 고민할 필요가 없다. 이미 2*2 사각형을 채우는 경우의 수를 알고있기 때문이다.

 

또한, 1*2 사각형 두개를 = 모양으로 놓고, 남은 2*1 사각형을 어떻게 채울지 고민해보면 되는데, 이 역시, 2*1 사각형을 채우는 경우의 수를 알고 있기 때문에, 더해주기만 하면된다. 

 

즉, 피보나치 수열의 형태를 띄고 있음을 파악할 수 있다.

 

2*3 사각형을 채우는 경우의 수는 2*2 사각형 경우의 수 + 2*1 사각형 경우의 수임을 알 수 있다. 

 

마찬가지로, 2*4 사각형의 경우, 2*3 사각형 경우의 수 + 2*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]=2; // 2*2 사각형 경우의 수
		for(int i=2;i<n;i++) {
			Dp[i]=(Dp[i-1]+Dp[i-2])%10007;  // 문제에서 10007로 나눈 나머지 값을 요구
		}
		System.out.println(Dp[n-1]); //2*n 사각형 경우의 수
	}
}