[DP] 2133 3*n 타일링문제

이해하기 까지 오래걸렸던 문제였다.

일단 홀수에서는 주어진 타일만으로 타일링을 할 수 없다. 그러므로 n이 짝수일 때만 값을 수할 수 있다.

n = 2인 경우

-> 가능한 경우의 수는 3개이다.

 

n = 4인 경우

1. 일단, dp[2]인 경우에 2만큼이 공간이 늘어난 것이므로 dp[2]*3으로 계산

2. 1번 경우에 더불어 dp[4]일때만 가능한 경우가 있다. 이 경우 2가지를 더한다.

-> 따라서 가능한 경우의 수는 11개이다.

 

n = 6인 경우

1. dp[4] 인 경우에 2만큼의 공간이 늘어난 것으로 dp[4]*3

2. 1번의 경우는 [()()()()]*[()()] 이지만 2번에서 고려해 주어야 할 경우는 [()()]*[()()()()]이다. 따라서 이 경우를 생각하면 dp[2]의 경우에 n이 4인 경우에서만 발생하는 특별한 경우의 수 2개를 곱해서 dp[2]*2이다.

3. 마지막으로 6일때만 발생하는 특별한 경우의 수를 2개 더한다.

-> 가능한 경우의 수는 33+ 6 + 2 = 41

 

** 2번에서 이해가 안하는 부분이 있어서 한참 고민했다. 1번에서 고려한 [()()()()]*[()()]인 경우에서 [()()]*[()()()()]인 경우를이미계산한 것이 아닌지해서 고민했다. 그렇게 생각한 이유는 dp[4] 에 이미 특별한 경우의 수 2가 포함되었다고 생각했고 이게 2번의 경우도 함께 포함이 되어있다고 생각했다. 하지만 실질적으로 보면 dp[4] * dp[2]를 계산한 것이므로 앞의 4개에 대한 특별한 경우의 수는 포함되어 있지만 4가 오른쪽에 올 떄 특별한 경우의 수는 포함되어 있지 않다. 즉 dp[4] * dp[2]에 대한 경우의 수와 dp[4]가 오른쪽에 왔을 때 특별한 경우의 수 2개를 더해주어야 한다. 여기서 2번에서 dp[4] * dp[2] 를 하지 않는 이유는 이렇게 하면 1번과 겹치는 경우의 수가 발생하기 때문이다. 따라서 4가 오른쪽에 있을 때 특별한 경우의 수 2개만을 더해주면 된다. 

 

public class Main {
	static int dp[], arr[];
	static int max;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		int n = sc.nextInt();
		sc.close();
	
		dp = new int[n+1];

		dp[0] = 1;
		dp[1] = 0;
		if(n > 1)
			dp[2] = 3;
		
		for(int i = 4; i <= n; i += 2) {
			dp[i] = 3*dp[i-2];
			for(int j = 0; j < i-2; j += 2) {
				dp[i] += dp[j] * 2;
			}
		}
		System.out.println(dp[n]);
	}
}