[백준,BOJ 2133] 타일 채우기( JAVA 구현)

-내 생각 및 해법

  이 문제 역시 타일 채우기 문제로, 예전에 유튜브 강의를 통해 접해 봤던 문제였다. 각 n의 경우에 따라서 타일의 모양을 그려보면 2x1, 1x2크기의 타일밖에 존재하지 않기 때문에 3xN크기의 타일을 채울 때, n이 1, 3, 5... 등 홀수의 경우에는 채울 수 없다는 것을 알 수 있다. 또한 n이 2일 때는 3개, 4일 때는 2의 경우의 수에서 새로운 모양 2가지가 등장해 총 11가지의 수가 등장한다. 이러한 새로운 모양은 n이 짝수로 증가할 때마다 2가지씩 새로운 모양이 등장하기 때문에 점화식을 세워보면, 

dp [n] = dp [n-2] * 3 + dp [n-4] *2 + dp [n-6] * 2.... 식으로 증가하게 된다. 

 

  이 때 주의하지 못했던 점이 있는데 바로 n이 0일 경우는 아무것도 채우지 않는 경우가 되는데, 이 경우 또한, 1로 생각해주어야 한다. 왜냐하면 위의 공식대로 n이 4일 경우를 계산해보면, dp [4] = dp [2] *3 + dp [0] *2가 되는데, 0을 고려하지 않아 버리면, dp [4]는 9가 될 것이다. 이는 2의 경우의수로 4만큼의 타일을 채웠을 경우밖에 되지 않기 때문에 새롭게 생긴 두 가지 모양이 반영되지 않는다는 것을 알 수 있다. 

 

import java.util.*;
import java.math.*;
public class Main {
	
	static int dp[] ;
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		dp = new int[31];
		dp[0] =1; // 0일 때 1을 고려해준다.
		dp[1] = 0;
		if(n>1)
			dp[2] = 3;
		
		for(int i=4;i<=n;i+=2) { // 4부터 2씩 증가반복
			dp[i] = 3*dp[i-2]; // i-2번째 dp값 *3
			for(int j=0;j<i-2;j+=2) { // 0부터 i-2번 째 수보다 작은 경우 반복
				dp[i]+=dp[j] * 2; // 위에 dp[i-2] *3 한 값에 계속해서 더해준다.
			}
		}
		
		System.out.println(dp[n]);
	
				
		
		
			
	}
	
}