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

문제 출처

www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

문제 설명

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

 

입력

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

 

출력

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

 

예제

입출력 예

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
 
public class Main {
    static int[] dp;
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        dp = new int[31];
        dp[0] = 1;
        dp[1] = 0;
 
        if(num > 1)
            dp[2] = 3;
        
        for(int i = 4; i <= num; i+=2) {
            dp[i] = 3 * dp[i-2];
            for(int j = 0; j < i-2; j+=2) {
                dp[i] += dp[j] * 2;
            }
        }
       System.out.println(dp[num]);
    }
 
}