11726번: 2×n 타일링

#include<iostream>
 
using namespace std;
 
int main(void) {
    int arr[1001];
    int    n;
 
    cin >> n;
    arr[1] = 1;
    arr[2] = 2;
    for (int i = 3; i <= n; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
    }
    cout << arr[n] << "\n";
}

 

타일링을 해주는 DP 문제이다. DP의 기초 문제라고 할 수 있다. 다만들기 전 가로 1, 가로 2로 할 수 있는 것들을 더해줘서 점화식 DP[n] = DP[n - 1] + DP[n - 2] 이런 식으로 만들어주면 된다.