[BOJ/C++] 11726 2xn 타일링

동적 계획법을 이용해 문제를 해결할 수 있습니다.

N=1 인 경우

2x1

N=2 인 경우

1x2, 1x2
2x1, 2x1

N=3 인 경우

2x1, 1x2, 1x2
1x2, 1x2, 2x1
2x1, 2x1, 2x1

해당 경우의 수를 통해 다음과 같은 점화식을 얻을 수 있습니다.

$DP[N] = DP[N-1] + DP[N-2]$

// boj s3 11726
// 2xn 타일링
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static long long DP[1001] = {0};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    DP[1]=1;
    DP[2]=2;

    for(int i=3; i<1001; i++)
        DP[i]=(DP[i-1]+DP[i-2])%10007;
    
    cout << DP[N];


    return 0;
}