문제링크

C++

#include <iostream>

using namespace std;

int memo[1001];
int n;

void dp(int n);

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    dp(n);

    cout << memo[n] << "\n";
}

void dp(int n){
    memo[0] = 1;
    memo[1] = 1;
    for (int i = 2; i <= n; i++){
        memo[i] = (memo[i - 1] + memo[i - 2] * 2) % 10007;
    }
}

• DP로 해결.
• 2*n 크기의 공간을 채우는데에는 2*(n - 1)의 공간을 채우고 세로로 길쭉한 블럭을 놓는 경우(한 가지)와, 2*(n - 2)의 공간을 채우고 2*2크기의 블럭을 넣는 경우, 가로로 긴 블럭 두 개를 넣는 경우(두 가지)가 있다.
• 따라서 $memo[i] = memo[i - 1] + memo[i - 2] * 2$의 점화식이 도출.
• $O(n)$