[백준 11726] 2×n 타일링

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

다음과 같이 두개의 기본 도형이 존재한다.

N번째 도형(2xN)을 만들 때 N-2번째 도형과 N-1번째 도형에 기본도형을 덧붙여서 만들 수 있다. 중복을 피하기 위해 한쪽 방향에만 계속하여 덧붙인다.

N-2번째 도형에는 2x2 기본도형을 오른쪽(왼쪽)에 붙이고 N-1째 도형에는 2x1 기본도형을 오른쪽(왼쪽)에 붙여서 만들 수 있다.

점화식 

arr[0] = 1

arr[1] = 2

arr[n] = arr[n-1] + arr[n-2]

C++ code

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