[백준 BoJ] 2133 - 타일채우기

dp[4]=11까지는 생각을 했지만 그 이후에 답이 안나와서 다른사람의 블로그를 참고했다.

 

#include<iostream>

using namespace std;
int dp[32];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	dp[0] = 1;
	dp[1] = 0;
	dp[2] = 3;

	for (int i = 4; i <= N; i+=2) {
		dp[i] = dp[i - 2] * dp[2];
		for (int j = i - 4; j >= 0; j -= 2) {
			dp[i] += dp[j] * 2;
		}
	}
	cout << dp[N];
}

• 다이나믹 프로그래밍
• 참고 : https://yabmoons.tistory.com/536