백준 11726 - 2xN 타일링

1) 점화식
dp[x]를 x번째 2 * x까지의 직사각형을 채우는 경우의수라고 정의하겠습니다.
이 dp테이블의 초기값을 정해보면,
dp[1] = 1, dp[2] = 2가 될것입니다.
int x (x >= 3)의 dp값의 경우는,
dp[x] = dp[x- 1] + dp[x-2]가 됩니다.

그 이유는 현재 x번째 까지 채우는 경우의수는,
x - 1까지 채운거에서 세로 하나 채우는 경우 의수 +
x - 2까지 채운거에서 가로 2개 채우는 경우의수 이기 때문입니다.
참고로 x - 2채운거에서 세로 2개 채우는 경우의수는
x - 1까지 채우고 세로 1개 채우는 경우와 동일하기에 처리하지 않습니다.
그리고 modular 처리만 잘 해주면 됩니다.

2) source code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pi 3.1415926535
#define pii pair<int,int>
using namespace std;

int dp[10101];

int main(void){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    int n;
    cin >> n;
    dp[1] = 1;
    dp[2] = 2;
    //dp[x] = dp[x - 1] + dp[x - 2]
    for(int i = 3; i<= n; i++){
        dp[i] = dp[i - 1] + (dp[i - 2]) % 10007;
    }
    cout << dp[n] % 10007;

    return 0;
}

타일링 문제중 가장 쉬운 문제입니다.
현재 상태를 가까운 이전 상태로 표현하기 위한 노력을 계속 하시면 됩니다.
그리고 경우의수 문제도 마찬가지로 현재 상태가 되기 위한 경우의수를
이전 상태가 되기 위한 경우의수의 조합으로 표현하려는 노력을 하셔야만 합니다.