Level 2. 2 x n 타일링

Level 2. 2 x n 타일링

 

 

예제를 참고해 분석해보니 길이가 5일 경우, 5C0 + 4C1 + 3C2가 되는 것 같아서 구현해보았으나 틀렸다.

 

// 이 풀이는 틀린 풀이다.
#include <iostream>
#include <vector>

using namespace std;

int solution(int n)
{
    int answer = 0;
    const int P = 1'000'000'007;
    vector<int> factorials(n + 1, 1);

    for (int i = 2; i <= n; ++i)
        factorials[i] = ((i % P) * factorials[i - 1]) % P;

    for (int i = n, j = 0; i >= j; --i, ++j)
        answer += factorials[i] / factorials[i - j] / factorials[j];

    return answer;
}

 

도저히 모르겠어서 힌트를 참고해보니 그냥 피보나치 수열과 모듈러 연산에 관한 문제였다고 한다..

 

계단 문제와 같이, n - 1번째 계단까지 올라가는 경우의 수에 n을 더한 값이 n번째 계단으로 올라가는 경우의 수가 되는 것과 같다.

 

#include <iostream>
#include <vector>

using namespace std;

int solution(int n)
{
    vector<int> v(n + 1, 1);
    const int P = 1'000'000'007;

    for (int i = 2; i <= n; ++i)
        v[i] = (v[i - 1] + v[i - 2]) % P;

    return v[n];
}