(프로그래머스 c++)2 x n 타일링

DP를 이용하면 된다.

어떻게 풀면 될까 고민하다가 n을 1부터 차례대로 넣어봤을 때의 값을 계산해 보았다.

하다보니 피보나치와 같은 결과를 얻을 수 있어서 DP의 피보나치를 사용하였다..!

#include <string>
#include <vector>

using namespace std;
int arr[600001] = {0, };

int solution(int n) {
    arr[1] = 1;
    arr[2] = 2;
    
    for(int i = 3; i <= n; i++)
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;

    return arr[n];
}