2133_Tri Tiling(DP)

3 * n 타일에 2 * 1 타일을 얼만큼 넣을 수 있는지 푸는 문제이다.    
짝수 일 때만 만들어지고 끝에 2와 4가 남았을 때 점화식이 만들어지는 것 같아서,   
`DP[n] = DP[n - 2] * 3 + DP[n - 4] * 2 `   으로 했는데 원하는 값이 나오지 않았다.    
다시 고민하였을 때, `DP[n] = DP[n - 2] * 3 + DP[n - 4] * 2 + DP[n - 6] * 2 + ... DP[0] * 2 + 2  ` 
이런식으로 2개씩 계속 추가적으로 생산이 되는 것을 알 수 있었다. 

 

#include<iostream> 
 
using namespace std; 
 
int main(void) { 
int n; 
int dp[31] = { 0 }; 
 
dp[0] = 0; dp[1] = 0; dp[2] = 3; 
cin >> n; 
for (int i = 4; i <= n; i += 2) { 
dp[i] += dp[i - 2] * 3; 
for (int k = 4; k <= i; k += 2) { 
dp[i] += dp[i - k] * 2; 
} 
dp[i] += 2; 
} 
cout << dp[n] << '\n'; 
}