[14852] 타일 채우기 3

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

14852번: 타일 채우기 3

<문제>

점화식을 설계하는 난이도도 있지만, 이를 (TLE 안나오게) 잘 구현하는 난이도도 있다.

dp[i] = 3 * dp[i - 2] + 2 * dp[i - 1];

여기까지는 간단하게 생각할 수 있지만, n>=3일때마다 고유한 모양이 나타난다.

해당 부분을 단순하게 구현하면 TLE를 피할 수 없으므로, dp[n]으로 구하던 것을 2차원으로 바꾸어,

고유한 모양을 dp[n][1], 전체를 dp[n][0]에 넣어준다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
ll n, dp[1000001][2];
int main(void) {
    cin >> n;
    dp[0][0] = 0;
    dp[1][0] = 2;
    dp[2][0] = 7;
    dp[2][1] = 1;
    int i;
    for (i = 3; i <= n; i++) {
        dp[i][1] = (dp[i - 1][1] + dp[i - 3][0]) % MOD;
        dp[i][0] = (3 * dp[i - 2][0] + 2 * dp[i - 1][0] + 2 * dp[i][1]) % MOD;
    }
    cout << dp[n][0] % MOD;
    return 0;
}