C++로 해결하는 도미노·트로미노 타일링 문제

문제 소개

도미노(Domino)와 트로미노(Tromino), 두 가지 종류의 조각이 있다고 가정해 봅시다. 이 조각들은 아래 그림과 같이 자유롭게 회전하여 배치할 수 있습니다.

문제 정의

타일링(tiling)에서는 보드 위의 모든 칸이 반드시 타일로 덮여 있어야 합니다. 두 타일링 결과는 4방향(상하좌우)으로 인접한 두 칸 중에서, 정확히 한쪽 타일링에서만 그 두 칸이 동일한 타일로 덮여 있는 경우에만 서로 다른 것으로 간주합니다.

N이 주어졌을 때, 2×N 크기의 보드를 타일링할 수 있는 서로 다른 방법의 수를 구하는 것이 목표입니다.

예를 들어 입력이 3이라면 출력은 5가 됩니다. 아래와 같은 배치들이 가능하기 때문입니다.

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

여기서 서로 다른 문자는 서로 다른 타일 조각을 의미합니다.

풀이 접근법: 동적 계획법(DP)

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

dp[i] = 2 × dp[i-1] + dp[i-3]

이 점화식은 i번째 열까지 채우는 경우의 수가, 직전 상태에 세로 도미노 하나를 추가하는 경우와 특수한 트로미노 배치를 고려하는 경우의 합으로 표현되기 때문입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

크기가 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]을 반환합니다.

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 numTilings(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.numTilings(3));
}

입력

출력

정리

이 문제는 겉보기에는 복잡해 보이지만, 규칙성을 찾아 점화식을 세우면 O(N) 시간 복잡도로 해결할 수 있는 대표적인 동적 계획법 문제입니다. 값이 커질 수 있으므로 10⁹+7로 나눈 나머지를 취하는 모듈러 연산을 잊지 않는 것이 중요합니다.