백준 2133 : 타일채우기

코드

#include <iostream>

using namespace std;

int dp[31];

int main(){
	int n;
	cin >> n;
	
	dp[0] = 1;
	dp[1] = 0;
	dp[2] = 3;
	
	if(n%2 == 1) cout << "0";
	else{
		for(int i = 4; i <= n; i = i+2){
			dp[i] = 3*dp[i-2];
			for(int j = i-4; j >=0 ; j = j - 2){
				dp[i] += 2* dp[j];
			}
		}
		cout << dp[n];
	}
	
	
	return 0;
}

알게된 점

참.. 이게 수학문젠지 알고리즘문제인지..

점화식을 생각하는게 참 어렵습니다.

dp는 점화식 생각이 참 중요한 문제 같습니다..