[백준] 2133번 타일 채우기

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

2133번: 타일 채우기

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

+2마다 예외 모양이 존재

중복되는 부분 제거

 

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

public class Main {

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int dp[] = new int[n+ 1];
        dp[0] = 1;

        for(int i = 2; i <= n; i=i+2) {
            dp[i] = dp[i-2] * 3;
            for(int j=0; j <i-2; j=j+2) {
           	 dp[i] = dp[i] + ( dp[j] * 2 );
            }
        }

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

}