[프로그래머스] 3 x n 타일링

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

2 x n 타일링과 유사하지만 조금 더 생각해야하는 동적 계획법 문제이다. 우선 홀수의 경우는 타일링이 불가능하다는 것을 알 수 있다. 그렇다면 짝수의 경우를 생각해봐야한다.

우선 3 x 2 를 타일링하는 경우를 생각해보자.

2의 경우 아래와 같이 3가지 경우가 가능함을 쉽게 알 수 있다.
즉, f(2) = 3 이다.

다음은 3 x 4을 타일링하는 경우이다.

2 x n 타일링에서 처럼 2 x 3 에서 했던 경우를 이용해야할 것 처럼 보인다. 2 + 2 = 4이므로 f(4) = f(2) x f(2) 라고 생각할 수 있지만, 3 x 4 에서만 가능한 타일링 방법이 2개 있다.

따라서 f(4) = f(2) x f(2) + 2 가 되어 f(4) = 11 이 된다.

3 x 6과 3 x 8을 살펴보면 마찬가지로 해당 경우에만 가능한 타일링 방법이 2가지가 있다는 것을 알 수 있다.

그리고 6의 경우는 다음과 같이 타일링을 계산할 수 있다.

이것을 n으로 확장해서 점화식을 구해보면
f(n) = f(n-2) x f(2) + f(4)' x f(n-4) + f(6)' x f(n-6) + ... + f(n-2)' x f(2) + 2 가 된다. 여기서 f(4)', f(6)' ... f(n-2)'는 각 경우에만 가능한 타일링 방법이므로 2이다. 그리고 f(2) = 3 이므로 식을 정리하면 f(n) = 3 x f(n-2) + 2(f(n-4) + f(n-6) + ... + f(2)) + 2가 된다.

아래의 코드에서는 점화식을 좀 더 간단하게 하기 위해서 f(0) = 1로 초기화해서 계산했다. 그리고 배열을 long long으로 초기화해서 구현하였다.

코드

C++

#include <string>
#include <vector>
#include <algorithm>
#define DIV 1000000007
using namespace std;

long long dp[5001];

int solution(int n) {
    if (n % 2 == 1) return 0;
    dp[0] = 1;
    dp[2] = 3;
    for (int i = 4; i <= n; i += 2) {
        dp[i] = dp[2] * dp[i - 2];
        for (int j = 0; j <= i - 4; j += 2)
            dp[i] += (2 * dp[j]);
        dp[i] %= DIV
    }
    return dp[n];
}

Python3

DIV = 1000000007

def solution(n):
    if n % 2 == 1:
        return 0
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[2] = 3
    for i in range(4, n + 1, 2):
        dp[i] += (dp[i - 2] * dp[2])
        for j in range(0, i - 3, 2):
            dp[i] += (dp[j] * 2)
        dp[i] %= DIV
    return dp[n]