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

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

풀이

입력값에 따른 출력값이 피보나치 수열과 비슷하게 증가합니다.

 

n이 1일 때 방법의 수는 1이고, 2일 땐 2, 3일 땐 3, 4일 땐 5 ... 입니다.

 

#include<iostream>

using namespace std;

int DP[1001];

int main(void)
{
    DP[1] = 1;
    DP[2] = 2;

    int n; cin >> n;

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

    cout << DP[n];

    return 0;
}

반례

Input

10

Output

89

 

Input

500

Output

9495

 

Input

1000

Output

1115