2×n 타일링 11726

문제

접근 방법

직접 하나씩 세보았다.
1 2 3 5 8 13 21
규칙이 보였다.
n-1, n-2를 더하면 n의 숫자가 나오는 것이다.
1의 경우 | 1개이다.
2의 경우 = , ‖ 2개이다.
3의 경우 =| , ‖| , |= 3개이다.
4의 경우 =‖ , ‖‖ , |=| , == , ‖= 5개이다.
n-1개에 짝대기를 한 개 더 긋거나
n-2개에 =을 한 개 추가하는 방식이라고 볼 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int arr[1001], n;
    cin >> n;
    arr[1] = 1, arr[2] = 2;
    for (int i = 3; i <= n; ++i)
    {
        arr[i] = (arr[i - 2] + arr[i - 1]) % 10007;
    }
    cout << arr[n];
}

풀이

접근 방법에서 이야기한 대로 i-2와 i-1의 값을 더하여 이어 나가면 된다.