[백준/C++]11726번 : 2×n 타일링

문제

 

https://www.acmicpc.net/problem/11726

---

Algorithm

규칙을 찾기 위해 n=1인 경우부터 세보니, n=k일 때 그 경우의 수는 (n = k-2 일 때의 경우의 수) + (n = k-1 일 때의 경우의 수)와 같다.

 

---

 

 

Code

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int dp[1001] = {0};
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i=3;i<=n;i++)
    {
        dp[i] = (dp[i-2] + dp[i-1]) % 10007;
    }
    
    cout << dp[n];
    
    return 0;
}