[JAVA/DP] 백준 2133 타일 채우기

1. 문제

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

2. 풀이

• DP를 사용해서 풀이한다.
• 2X1, 1X2 타일을 이용해 채우므로, 3XN에서 N이 홀수일 경우 타일로 채워질 수 없다. 자바 배열에서는 배열 선언시 0으로 초기화 되므로 별도로 값을 초기화해주지 않아도 된다.
• 경우를 2가지로 나누어서 생각한다.
  1. 3X2를 채울 수 있는 경우는 3개이다.

     

     • N-2개의 타일을 채운 경우 뒤에 2X1을 채워넣는다고 생각하면, DP[N] += DP[N-2] * 3이다.
  2. 4X2, 6X2, 8X2.... 4 이후 2의 배수마다 2가지 방법으로 칸을 채울 수 있는 방법이 추가된다.

     

     • 즉, (1) N-4까지 타일로 채우고 4X2 타일로 채운 경우, (2) N-6까지 타일로 채우고 6X2 타일로 채운 경우.... 이런식으로 타일을 추가로 채울 수 있는 방법이 있다.
     • 4X2 타일이나 6X2 타일 등 위의 추가적인 방법으로 채울 수 있는 방법은 모두 2가지 이므로, for문을 사용해서 현재의 DP 값에 이 경우들을 누적해서 합해준다. 이를 코드로 표현하면 아래와 같다.

       for(int j = 4; j <= i; j += 2) {
       	dp[i] += dp[i-j] * 2;
       }​

 

3. 코드

import java.io.*;

class Main{
	
	public static void main (String[] args) throws java.lang.Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[31];
		
		dp[0] = 1;
		dp[2] = 3;
		
		for(int i = 4; i <= n; i+=2) {
			dp[i] += dp[i-2] * 3;

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