백준[11726] - 2*n 타일링

문제

백준 11726 문제 보기

접근 방법

bottom-up 방식의 dp를 활용해 문제 접근을 했다. 길이가 1인 타일이 추가될 때와 2인 타일이 추가될때의 경우를 계산해 식을 세웠다.
점화식은 다음과 같다.
dp[n] = dp[n-1] + dp[n-2]

코드

#include <iostream>

using namespace std;

int n;
int dp[1001];

int main() {

    cin >> n;

    dp[0] = 1;
    dp[1] = 1;

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

    cout << dp[n];

    return 0;
}