[백준 11727] 2xn 타일링 2 c++

문제 링크 : 백준 11727 2xn 타일링 2

문제

2xn 직사각형을 2x1과 2x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

• 예시
  • 입력 : 2 / 출력 : 3
  • 입력 : 8 / 출력 : 171
  • 입력 : 12 / 출력 2731

풀이

직접 다 그려보면서 점화식을 찾았다. 점화식은 f(n) = (f(n-1) + f(n-2) * 2)

코드

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 1000

int cache[MAX];

int main() {
    int n;
    cin >> n;

    cache[1] = 1;
    cache[0] = 1;

    for(int i = 2; i <= n; i++) {
        cache[i] = (cache[i-1] + cache[i-2] * 2) % 10007;
    }

    cout << cache[n] << endl;

    return 0;
}