[백준 11727] 2×n 타일링 2

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

https://neroren.tistory.com/78 과 유과 유사한 문제

위 문제에서 2x2 기본도형이 하나 더 추가되었다.

이 경우 n-2번째 도형에 붙일 수 있는 2x2 기본도형이 2가지 이므로 곱하기 2를 해주어야 한다.

 

점화식 

arr[0] = 1

arr[1] = 3

arr[n] = arr[n-1] + 2 * 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] = 3;
    for(int i = 2; i < n; i++){
        arr[i] = (arr[i-1] + 2*arr[i-2]) % 10007;
    }
    cout << arr[n-1];
    delete[] arr;
    return 0;
}