C++을 활용한 도미노와 트로미노 타일링 경우의 수 계산 방법

문제 개요

도미노(Domino)와 트로미노(Tromino)라는 두 가지 모양의 조각이 있다고 가정해 보겠습니다. 도미노는 2×1 크기의 직사각형 모양이고, 트로미노는 'L'자 형태의 모양입니다. 두 조각은 아래 그림과 같이 회전하여 사용할 수 있습니다.

숫자 n이 주어졌을 때, 이 두 종류의 조각으로 2×n 크기의 보드를 완전히 채우는 배치의 가짓수를 구해야 합니다. 타일링 문제에서는 보드의 모든 칸이 반드시 하나의 타일로 덮여 있어야 한다는 점에 유의하세요.

예시

입력이 3이라면 출력은 5가 됩니다. 가능한 배치는 다음과 같습니다.

[XYZ XXZ XYY XXY XYY]
[XYZ YYZ XZZ XYY XXY]

여기서 서로 다른 문자는 서로 다른 타일을 나타냅니다.

풀이 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 점화식은 다음과 같습니다.

크기가 N+5인 dp 배열을 생성하고, 초기값을 설정합니다. dp[1] = 1, dp[2] = 2, dp[3] = 5
i가 4부터 N까지 순회하면서 다음 점화식을 적용합니다.
dp[i] = 2 × dp[i-1] + dp[i-3]
최종적으로 dp[N]의 값을 반환합니다.

이 점화식은 마지막 열을 채우는 방식에 따라 경우를 나누어 유도할 수 있습니다. 세로 도미노 하나로 끝나는 경우(dp[i-1]), 가로 도미노 두 개로 끝나는 경우(dp[i-2]), 그리고 트로미노가 관련된 경우들을 종합하면 위와 같은 간결한 식이 성립합니다.

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int add(int a, int b){
    return ((a % MOD) + (b % MOD)) % MOD;
}

class Solution {
    public:
    int solve(int N) {
        vector <int> dp(N + 5);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;
        for(int i = 4; i <= N; i++){
            dp[i] = add(2 * dp[i - 1], dp[i - 3]);
        }
        return dp[N];
    }
};

main(){
    Solution ob;
    cout << (ob.solve(3));
}

입력

출력

정리

이 알고리즘의 시간 복잡도는 O(N), 공간 복잡도 역시 O(N)으로, 주어진 점화식만 정확히 이해하면 매우 효율적으로 문제를 해결할 수 있습니다. 결과값이 커질 수 있으므로 나머지 연산(MOD = 10⁹ + 7)을 활용해 오버플로우를 방지하는 것도 잊지 말아야 합니다.