C++:: 프로그래머스 < 2 x n 타일링 >

문제의 핵심은 점화식을 만드는 것이다.

f(n) 범째에 올수있는 패턴은 f(n-1) 에서 ㅣ 하나를 추가하는 것과 f(n-2)에서 =를 추가해주는 경우이다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    vector<long long> dp(n+1, 0);
    dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 5;
    for (int i=5; i<=n; i++) dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
    return dp[n];
}