[c++][BOJ][11726] 2 x n 타일링

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

11726번: 2×n 타일링

2 x n 크기의 직사각형을 1 x 2 , 2 x 1 타일로 채우는 방법의 수를 구하는 문제입니다.

 

2 x k 크기의 직사각형을 채우는 것은 ,

 

1. 2 x ( k - 1 ) 크기의 직사각형에 2 x 1 짜리 타일 하나 추가하는 것과

 

2. 2 x ( k - 2 ) 크기의 직사각형에 1 x 2 짜리 타일 두개를 추가하는 것과 같습니다.

 

즉 , k번째를 채우는 방법의 수는 k - 1 과 k - 2 를 더하는 것과 같습니다.

 

이 수는 피보나치 수열로 나타낼 수 있는데 , 더할때마다 10007로 나누어야 에러가 나지 않습니다.

#include <iostream>
using namespace std;

int main(){
    int n ;
    cin >> n;
    
    int count = 0;
    
    int arr[1001] = {0};
    arr[1] = 1;
    arr[2] = 2;
    
    int index = 3;
    
    while(index <= n){
        arr[index] = (arr[index-1] + arr[index-2]) % 10007;
        index++;
    }
    
    cout << arr[n];
}