백준 2133번 : 타일 채우기 (java)

문제를 읽고 처음 dp 타일 연습문제와 비슷하다고 생각하여 쉽게 접근하였다. 하지만 fail 이 뜸.

 

잘 이해하지 못해서 해설 여러개를 보았다. 그 중에서 가장 이해가 잘 된 해설이다. 

[출처]

https://fbtmdwhd33.tistory.com/79  

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Baekjoon2133 {
	static int[] dp;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());

		dp = new int[n + 1];
		dp[0] = 1; // 아무것도 선택하지 않았다도 1로 포함
		dp[1] = 0;

		if (n > 1) {
			dp[2] = 3;
		}

		for (int i = 4; i <= n; i += 2) { // 2씩 증가. 짝수니까
			dp[i] = 3 * dp[i - 2]; // i-2 번째 에다가 3을 곱함. 처음만 3을 곱한다. 3개 경우의 수니까
			for (int j = 0; j < i - 2; j += 2) { // i-2번 째 수보다 작은 경우 반복
				dp[i] += dp[j] * 2; // dp[i] 값에 계속 더해 준다
			}
		}

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

	}


}