[백준][c++] 11727번: 2×n 타일링 2

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

문제 해석

• dp(다이나믹 프로그래밍)을 이용하여 2xn의 타일을 채울수 있는 경우의 수 구하기

알고리즘 분류

• 다이나믹 프로그래밍

풀이

•  arr[i] = (arr[i-1] + arr[i-2]*2) 라는 규칙을 찾아내 dp배열 채우기

코드

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    int arr[1001];
    arr[1] = 1;
    arr[2] = 3;
    cin >> n;

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