[boj][c++] 11726 2xN타일링

11726 2xN 타일링

전형적인 다이나믹 프로그래밍 문제였다. n이 1부터 5일때의 경우의 수를 하나씩 그렸는데 아래와 같다.

이 그림을 표로 정리하면 아래와 같다.

1	2	3	4	5
1	2	3	5	8

뭔가... 이제 이런 표만 보면 너무 익숙한 느낌이 든다. 응 피보나치~
설마하고 n이 6일 때도 머리 굴려가며 그려봤는데 내 계산으로는 13개의 경우의 수밖에 찾을수 없었다. 그런데 이정도만 알아내도 의심할 여지 없는 피보나치 수열이었다.
피보나치 수열의 구현 자체는 간단하기 때문에 상당히 짧은 코드가 완성됐다.

#include       <iostream>
using namespace std;

int arr[1001];

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