백준 11727번 - 2xn 타일링2

https://www.acmicpc.net/problem/11727

2*n크기의 직사각형을 채울 때
n-1번째에서 가로의 길이가 1 직사각형을 더해주고
n-2번째에서 가로의 길이가 2인 직사각형을 더해주면 된다.


처음에 문제에 해당하는 답이 안나와서 왜 안나올까 고민을 하다가
가로의 길이가 2인 직사각형을 더해줄 때 1가지가 아닌 2가지 경우를 반영해서 해결할 수 있었다.

즉 가로의 길이가 2인 직사각형에서 
세로의 길이가 1인 직사각형과 세로의 길이가 2인 직사각형을 같이 생각해야 한다.


점화식은 다음과 같다

dp[n] = dp[n-1] + dp[n-2]*2

(dp[n]은 길이가 n일 때 직사각형을 채울 수 있는 방법의 수)

#include <iostream>
using namespace std;
 
int main(){
    
    int n;
    cin>>n;
    
    int dp[1001]={0,1,3};
    for(int i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]*2;
        dp[i]%=10007;
    }
    cout<<dp[n]<<endl;
    return 0;
}