[백준] 11726 2xn 타일링 C++ (DP)

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

1x2, 2x1 두 가지 블록을 사용해서 2xN 직사각형을 채우는 방법의 수를 구하는 문제이다.

N=5일 때 까지는 직접 그려보았다.

규칙을 찾았다
N번째일 때 방법 수 = N-2일 때 방법 수 + N-1일 때 방법 수
바로 앞의 두 수의 합이 값이되었다.
피보나치 수열과 비슷하다.

따라서 점화식은
d[n] = d[n-1] + d[n-2]
이다.

10007에서 나눈 나머지를 출력하라고 하였으므로 나눠준다.

#include<iostream>
using namespace std;

int main()
{
    int dp[100001];
    int n;
    scanf("%d",&n);

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

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

    }
    printf("%d\n", dp[n]);
    return 0;
}