[프로그래머스] 12902 3 x n 타일링 (C/C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12902

풀이

n이 홀수일 경우 조건을 만족하는 배치가 존재하지 않으므로, 짝수의 경우에만 고려해서 문제를 풀었다. 문제를 살펴보니 이전 상태가 이후 상태에 영향을 준다는 점에서, 동적 계획법을 적용하기로 했다. 동적 계획법 특성 상 $f(2)$, $f(4)$, $f(6)$ 등 작은 케이스부터 차례대로 값을 계산해 보았고, 아래와 같이 각 경우마다 새로운 모양의 배치 방법이 2가지씩 추가되는 것을 알 수 있었다.

$n = 4$

$n = 6$

$n = 8$

$f(n)$은 $f(n - 2)$에 $n=2$ 일 때의 기본 모양 3개를 붙인 것 + $f(n - 4)$에 $n=4$ 에서 새로 나온 모양 2개를 붙인 것 + $f(n - 6)$에 $n=6$ 에서 새로 나온 모양 2개를 붙인 것 + ... + $f(0)$에 $n=n$ 에서 새로 나온 모양 2개를 붙인 것 모두를 합한 값이 된다.

즉,

이고, 이를 합으로 표현하면

가 된다.

등차수열의 합을 통한 연산은 O(N^2)의 시간 복잡도를 가지므로, 별도의 변수를 통해 이전 합을 저장해두고 갱신하는 방식으로 구현했다.

소스 코드

#include <bits/stdc++.h>

#define MOD 1000000007

int solution(int n) {
    std::vector<long long> dp(n + 1);
    long long special = 0;

    dp[0] = 1;
    dp[2] = 3;
    for (size_t i = 4; i <= n; i += 2) {
        special = (special + dp[i - 4] * 2) % MOD;
        dp[i] = (3 * dp[i - 2] + special) % MOD;
    }

    return dp[n];
}