DP [백준 2133 타일 채우기] -java-

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

2133번: 타일 채우기

힌트

이번 타일 채우기 문제를 풀면서 느꼈던 것은 역시 알고리즘 문제는 규칙 찾기 문제이다 라는 것이다. 이 문제는 2XN 타일 채우기 문제와 매우 흡사하긴 하지만, 3XN 문제이다. 3XN타일을 채우는데 사용하는 타일은 1X2, 2X1이다. 그래서 N에 짝수가 들어가지 않으면 3XN타일을 채울 수 없다. 이 점에 착안을 두어서 규칙을 찾다 보면 빠르게 찾을 수 있다. 

코드 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		long[] dp = new long[N + 1];
		dp[0] = 1; //dp[2]=3을 만들기 위해서 ...
		
			for (int i = 2; i <= N; i += 2) {
				dp[i] = 3 * dp[i - 2];
				for (int j = i - 4; j >= 0; j -= 2) {
					dp[i] += dp[j] * 2;
				}
			}
		
		System.out.println(dp[N]);

	}

}