Approach
문제를 잘 보면 전체적으로 이전의 결과가 이후의 결과에 계속 영향을 주는 것을 알 수 있고
해당하는 경향성을 점화식을 통해 일반화해서 나타낼 수 있음을 쉽게 파악할 수 있다.
이 지점에서 DP문제를 떠올려 주면 된다.
다만, 이 문제에서 어느 블록을 이전에 썼는지를 파악해야 경우의 수를 더할 수 있으므로
각 타일의 종류마다 따로 DP를 할당해서 점화식을 세워주면 된다.
에를 들어
dp[i][1], dp[i][2], dp[i][3]을 각각 i번째 가로에 1 x 2, 2 x 1, 2 x 2 블럭을 사용했을 때의 경우의 수라고 하면 점화식을 다음과 같이 나타낼 수 있다.
$$ dp[i][1] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]$$
$$dp[i][2] = dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][3]$$
$$dp[i][3] = dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][3]$$
Code
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int dp[1001][3];
int main(void){
memset(dp, 0, sizeof(dp));
dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 1;
dp[2][3] = 1;
int n;
cin >> n;
for(int i = 3; i <= 1000; i++){
dp[i][1] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % 10007;
dp[i][2] = (dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][3]) % 10007;
dp[i][3] = (dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][3]) % 10007;
}
int result = (dp[n][1] + dp[n][2] + dp[n][3]) % 10007;
cout << result << "\n";
return 0;
}