# 백준 : 2xn 타일링 2(11727)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/edit/master/bj_11727_2xn%20tiling%202)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

#define MAX 1000

long long int dp[MAX + 1] = {0,};

int main(void)
{
    int value;
    cin>>value;
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 3;
    
    for(int i=3; i<=value; i++) {
        dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10007;
    }
    cout<<dp[value]<<endl;
    return 0;
}

풀이

이 문제도 전형적인 피보나치문제라서 포스팅을 할까말까 고민하긴했는데, 의외로 점화식을 푸는 과정이 꽤 까다로웠다. 엄밀히 말하면 문제에서 1x2 타일에 대한 소개를 하지 않아서 애를 먹었다.
(사실 전혀 상관없는 부분이기는 한데, 그래도 설명이 있는것과 없는 것이 의외로 신경이 많이 쓰였다는..)
어쨌든 계산해보면 tile[n - 2] * 2 + tile[n - 1] = tile[n] 이 된다.