[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]

이 문제는 동적계획법으로

첫 번째 타일이 세로로 있을 때(n-1)랑 2개의 타일이 가로로 되어있을 때(n-2)의 경우의 수를 합하는 것과 같다.

이는 피보나치 수열과 같으므로 같은 방법으로 풀면 된다.

#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[1001];
 
unsigned long long fibonacci(int n) {
    if (n == 1)
        return result[n] = 1;
    if (n == 2)
        return result[n] = 2;
    if (result[n] > 0)
        return result[n];
    else
        return result[n] = (fibonacci(n - 1) + fibonacci(n - 2))%10007;
}
 
int main() {
    int input;
    cin >> input;
    cout << fibonacci(input);
    return 0;
}