[백준] 타일 채우기

참고 : www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

- dp 문제

- 3xn 타일링 문제

- dp[i] =3 *dp[i-2] (i-2번째에서 가능한 모형 3가지 경우) + 2 *dp[i-4]~ dp[0] 까지 ( 각 단계에서 생기는 특수한 경우 2가지)

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[31];
        dp[0] = 1;
        dp[2] = 3;
        dp[4] = 11;
        for (int i = 4; i <= 30; i = i+2) {
            dp[i] = 3 * dp[i-2];
            for(int j = i-4; j>=0; j = j-2) {
                dp[i] += 2*dp[j];
            }
        }
        System.out.println(dp[N]);
    }
}