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

/* 백준 11727 2×n 타일링 2
https://www.acmicpc.net/problem/11727

* 문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

    = --> +--------+   | --> +---+   ㅁ --> +---------+
          |        |         |   |          |         |
          +--------+         |   |          |         |
          |        |         |   |          |         |
          +--------+         +---+          +---------+

    =|ㅁㅁㅁ==ㅁ||

* 입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

* 출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

* 예제 입력 1
2

* 예제 출력 1
3

* 예제 입력 2
8

* 예제 출력 2
171

* 예제 입력 3
12

* 예제 출력 3
2731

* 풀이

잘 모르겠는 경우에는 일단 하나씩 써 본다. 보고만 있으면 누가 풀어 주지 않기 때문에.

    n   경우의 수
    --------------------------------------------------
    1   1    | 의 경우 밖에 없음
    2   3    ||, =, ㅁ 총 3 가지의 경우가 존재
    3   5    |||, |=, |ㅁ, =|, ㅁ|
    4   9    ||||, ==, ㅁㅁ, ||=, ||ㅁ, |=|, |ㅁ|,  =||, ㅁ||
    5   19?  |||||, |==, |ㅁㅁ, |||=, |||ㅁ, ||=|, ||ㅁ|, |=||, |ㅁ||,
                    ==|, ㅁㅁ|, ||=|, ||ㅁ|, |=||, |ㅁ||, =|||, ㅁ|||,
                    =|=, ㅁ|ㅁ

그만 합시다. 이런 식으로는 계산이 힘드네요. 
하지만 한 번 이렇게 풀어서 써 보는 습관을 들이는 것이 좋습니다.
이제, 조금 고민을 해 봐야겠네요.

2xN 타일을 채울 수 있는 경우의 수를 P(N) 이라고 해 봅시다.
마지막 N 번째 타일을 놓을 수 있는 상황은

    ...|    P(N-1)
    .. =    P(N-2)
    .. ㅁ   P(N-2)
    (=, ㅁ 은 2칸짜리)

와 같고, 따라서, P(N) = P(N-1) + P(N-2) + P(N-2) 와 같이 되겠습니다.

Dynamic programming 이 답이네요.

구현은 매우 간단할 것 같습니다.
*/

#include <iostream>
#include <vector>

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);

	int n;
	std::cin >> n;

	std::vector<int> dp(n + 1, 0);

	dp[1] = 1;
	dp[2] = 3;

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

	std::cout << dp[n] << '\n';
}