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

#include <iostream>
#include <vector>
 
int DP[1001] = {};
 
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int N = 0;
    std::cin >> N;
 
    DP[1] = 1;
    DP[2] = 3;
 
    for (int i = 3; i <= N; ++i)
    {
        DP[i] = (DP[i - 1] + DP[i - 2] * 2) % 10007;
    }
 
    std::cout << DP[N];
 
    return 0;
}

아예 그려봤습니다.

4번까지 그리니까 답이 보이더라구요. 한번 그려보세요.

1번은  |

2번은  ||, =, ㅁ 입니다.

3번은  |||, |=, |ㅁ, =|, ㅁ| 입니다.

4번은 ||||, ||=, ||ㅁ, |ㅁ|, |=|, ㅁ||, =||, ==, ㅁㅁ

보이시나요? -2에서 =, ㅁ 두개추가 가능하니까 * 2, -1에서 | 하나만 추가 가능하기 때문에 * 1 입니다.