Level 2. 3 x n 타일링

Level 2. 3 x n 타일링

 

 

도저히 모르겠어서 어쩔 수 없이 보고 풀었다..

 

DP를 이용한 점화식 문제라는데, 1부터 대입해보며 규칙을 찾아 점화식을 만들어 해결하는 방법인 것 같다..

 

#include <iostream>

using namespace std;

int solution(int n)
{
    int DIV = 1'000'000'007;
    long pa = 1, a = 0, b = 0, c = 2;

    for (int i = 1; i < n; ++i)
    {
        long A = a, B = b;

        a = (c + pa) % DIV;
        b = c;
        c = (B + 2 * A) % DIV;
        pa = A;
    }

    return a;
}