[JAVA] 백준 2133번 【타일 채우기】

 

 

---

악--------

 

이 문제 엄청 간단한 문제일 줄 알았는데, 푸는데 엄청 오래 걸렸다.

 

그래서 내 공부계획에 영향을 주게된.. 알고리즘 한 문제 풀고 스프링 수업 들으려고 했는데 ㅜㅜ 아무튼

 

3*n 공간에 1*2,2*1 타일을 채우는 문제인데,

 

n이 홀수 일때에는 3*n = 무조건 홀수 이므로, 타일의 갯수가 짝수개밖에 없는 상황에서 홀수공간을 채우는 것은 불가능하므로 n이 홀수인 경우는 생각하지 않아도 된다.

 

이제 n이 짝수일때, 규칙을 찾아서 점화식을 세워야 한다.

 

 

 

먼저 n=2일때, 3가지 경우의 수가 나오는 것은 누구나 알 것이다. 

 

dp[2] = 3 을 초기값으로 지정한다.

 

n=4부터 규칙을 찾아야 한다.

 

n=4 일때, 먼저 한쪽 너비 2칸을 dp[2]로 채우는 경우의수만큼 채울 수 있고, 남은 너비 2칸도 dp[2] 경우의 수만큼 채울 수 있다.

 

하지만, 오른쪽 2개의 경우와 같이 dp[2]*dp[2] 경우에 포함되지 않는 예외 경우가 2개 발생한다.

 

dp[4]= dp[2]*dp[2] + 2 가 된다.

 

n=6일 때

 

 

먼저 오른쪽 너비 2칸을 dp[2]의 경우의 수 만큼 채우면 남은 4칸은 dp[4] 경우의 수만큼 채울 수 있다.

 

dp[4] 경우의 수에 dp[2]*dp[2] 경우의 수 까지 포함하므로 성립한다.

 

그리고 오른쪽 너비를 dp[4]만큼 채우고 남은 너비 2칸을 dp[2] 만큼 채우면 중복하는 경우의 수가 발생한다. 왜냐하면 위에서 말했듯이 dp[4] 경우의 수는 dp[2]*dp[2] 경우의 수를 포함하기 때문이다.

단적인 예로  위와 같은 경우는 dp[2]*dp[4] 에도 포함되고 dp[4]*dp[2] 경우의 수에도 포함되기 때문이다. 

 

따라서 dp[4]에서 발생한 예외 경우를 집어넣었을 때에만 새로운 경우의 수가 될 수 있다.

 

그리고 n=6일 때에도 역시 예외가 2개 발생한다.

 

즉. dp[6]=dp[2]*dp[4] + (dp[4]에서 발생하는 예외)*dp[2] + (dp[6]에서 발생하는 예외)

 

 

 

최종적으로

 

dp[n] = dp[2]*dp[n-2] + [ (dp[4]에서 발생하는 예외)*dp[n-4] + (dp[6]에서 발생하는 예외)*dp[n-6] ............

+(dp[n-2]에서 발생하는 예외)*dp[2] ] + (dp[n]에서 발생하는 예외) 

 

가 되고 각 케이스에서 발생하는 예외는 항상 2개가 나오므로

 

dp[n]=dp[2]*dp[n-2] +[ 2*( dp[n-4] +dp[n-6] .....+dp[2] ) ] + 2가 되는 것을 알 수 있다.

 

위 점화식을 코드로 나타내면 아래와 같다!

import java.util.Arrays;
import java.util.Scanner;

public class No_2133 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		long [] dp = new long [N+2];
		dp[2] = 3;
		for(int n=4;n<=N;n+=2) {
			dp[n]+=dp[n-2]*dp[2];
			for(int j=2;j<=n-4;j+=2) {
				dp[n]+=2*dp[j];
			}
			dp[n]+=2;
		}
		
		System.out.println(dp[N]);
//		System.out.println(Arrays.toString(dp));
	}
}