Dynamic Programming 백준 알고리즘 자바 2133 ‘타일 채우기’ 문제풀이

Problem

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

Input
첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

Output
첫째 줄에 경우의 수를 출력한다.

Solution

이해하는 데 너무 어려웠다… 우선 n=2일 때, d[2] = 3이다. 직접 그려보면 알 수 있다. 그리고 n은 짝수일 경우에만 타일을 채울 수 있기 때문에(그려보면 알 수 있다, 홀수는 항상 1칸이 남는다.) n%2 == 0 조건을 넣었다. d[4]는 32 사각형 두 개로 생각하면 d[2]d[2]의 경우의 수가 존재한다. 단, 34 모양일 때만 만들 수 있는 모양이 있는데 그것은 2가지 종류이다. 따라서 d[4] = d[2]d[2] + 2이다. d[6]은 34와 32 사각형이 있다고 생각하면 d[4]d[2]의 경우의 수가 존재하고, 36 일 때만 가능한 경우 2가지가 있다. 그런데 앞이 34와 32로 구성된 구조 말고도 앞이 32와 34인 구조도 생각해야한다. 그렇다고 d[2]d[4]를 또 더하면 중복 모양이 발생하기 때문에 34 일 때만 존재하는 특수 경우를 한 번 더 더해준다. (이때 큰 사각형은 36이므로 ‘34의 특수경우’ x ‘32의 경우’ 와 ‘32의 경우’ x ‘3*4의 특수경우’를 더 해준다.)

Code

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