[BOJ] 2133 타일 채우기 - JAVA

1. 문제

2133번: 타일 채우기

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

---

2. 풀이

1.  N이 홀수일 때, 그 경우의 수는 항상 0이다. 0을 출력하고 바로 끝낸다.

2.  N=4부터 특수 모양이 두 개씩 등장한다. 

dp[4] = dp[2] * dp[2] + 2 = dp[2] * 3 + 2 = 11

dp[6] = dp[4] * dp[2] + dp[2] * 2 + 2 = dp[4] * 3 + dp[2] * 2 + 2

dp[8] = dp[6] * 3 + (dp[6] * 2 + dp[4] * 2) + 2

dp[8]로 예를 들면, 길이 6:2로 나눈 경우의 수 + 길이 2 : 6칸 특수모양 경우의 수 + 길이 4 : 4칸 특수모양 경우의 수 + 8칸 특수모양 경우의 수를 모두 합친 값이다.

import java.io.*;
import java.util.*;

public class BOJ_2133_타일채우기 {
   public static void main(String[] args) throws IOException {
      Scanner in = new Scanner(System.in);
      int N = in.nextInt();
      if(N%2==1){
         System.out.println(0);
         return;
      }

      int[] dp = new int[N+1];
      dp[2] = 3;
      for(int i=4;i<=N;i+=2){
         dp[i] = dp[i-2]*3 + 2;
         for(int j=i-2;j>=4;j-=2){
            dp[i] += dp[i-j]*2;
         }
      }

      System.out.println(dp[N]);
   }
}

---

3. 결과

점화식 찾기 어렵다..