[백준][C++] 11727번 - 2×n 타일링 2

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

11727번: 2×n 타일링 2

---

풀이

1. 직사각형의 가로를 채우는 방법
   1. 2 * 1 -> 2칸 차지
   2. 2 * 2 -> 2칸 차지
   3. 1 * 2 -> 1칸 차지
2. n >= 3 일 때, n-1에서 가로가 1 늘어난 경우, n-2에서 가로가 2 늘어난 경우를 이용하여 문제를 해결
3. 가로가 2 늘어나는 경우의 수는 2가지 -> (n-2 결과) * 2 만큼 더해줘야 함
4. a[i] = (a[i - 1] + 2 * a[i - 2])

---

답

#include <iostream>
using namespace std;
int main()
{
    int n, a[1001];
    cin >> n;

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

    cout << a[n] << '\n';
    return 0;
}