2×n 타일링 2 11727

문제

접근 방법

2×n 타일링을 이해했다면 바로 해결법이 떠오를 것이다.
1X2 A
2X1 두 개를 B (구조상 2X1를 한 개만 쓸 수 없다),
2X2를 C라고 하고 작성해보자.
(A는 1의 값, B와 C는 2의 값이라고 볼 수 있다)
n이 1이면 A
2이면 AA, B, C
3이면 AA A, B A, C A, A B, A C
4이면 A B A, A C A, AA AA, B AA, C A A, AA B, AA C, B B, B C, C B, C C
3의 경우를 보면 2인 경우에서 3이 되려면 1인 값밖에 못들어가기에 A를 더 붙인 것을 볼 수 있다.
1인 경우에서 3이 되려면 A를 2개 붙일 수도 있지만 이미 2인 경우에서 고려됐기에 중복될 일이 없는 2의 값인 B 또는 C를 붙이는 것이다.
2×n 타일링에서는 2X1 두 개만 붙이면 됐지만, 이번 문제에선 2X2도 존재하기에 곱하기 2를 하면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int arr[1001], n;
    cin >> n;
    arr[1] = 1, arr[2] = 3;
    for (int i = 3; i <= n; ++i)
    {
        arr[i] = ((arr[i - 2] << 1) + arr[i - 1]) % 10007;
    }
    cout << arr[n];
}

풀이

기존 문제에서 2칸을 더하는 과정에서 1가지 경우가 더 추가됐기에 2배를 하면 끝난다.