[백준] 11727 2×n 타일링 2 C++ (DP)

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

---

---

점화식을 구하기 위해
몇 가지 예시를 직접 구해보자.
N=1일 때 => 1

N=2일 때 => 2

N=3일 때 => 3

N=4일 때 => 5

임을 알 수 있다.
이를 표로 나타내면 아래와 같다.

가로길이 N	1	2	3	4	...
채우는 방법	1	2	3	5	...

규칙을 찾아서 점화식으로 표현해보자.
d[1] = 1
d[2] = 2
를 정해주고 시작한다. N이 3인 경우부터 생각해보면
d[3] = 1+2 = d[1] + d[2] = 3
d[4] = 2+3 = d[2] + d[3] = 5

즉, d[i] = d[i-1] + d[i-2] 라는 점화식을 도출할 수 있다.

점화식
d[i] = d[i-1] + d[i-2]

어디서 많이 본 점화식이다. 피보나치 수열의 점화식과 동일하다.

---

#include <iostream>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

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

    for (int i = 3; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
    }
    printf("%d\n", dp[n]);
}