타일 채우기 2( BOJ 13976 )

문제 : https://www.acmicpc.net/problem/13976

13976번: 타일 채우기 2

 

문제 파악하기

3xN 크기의 벽을 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제입니다. 2xN 크기의 벽을 채우는 문제의 심화된 버전이라고 할 수 있습니다. 하지만 문제를 해결하는 과정은 2xN 크기의 벽을 채우는 문제와 동일한 방식으로 해결할 수 있습니다. 이전 상태를 사용할 수 있는 경우가 총 몇 가지인지 확인해서 점화식을 세우면 문제를 해결할 수 있습니다.

 

문제 해결하기

이렇게 타일을 채우는 문제는 가장 작은 경우부터 하나씩 확인해보면 됩니다. 여기서 중요한 점은 사용하는 블럭이 짝수의 크기를 가지고 있다는 점입니다. 따라서, 입력된 N이 홀수라면 2x1 크기의 타일로는 채울 수 없습니다. 즉, 가짓수는 0가지 입니다. 그리고 짝수인 경우에는 규칙을 찾아보면 됩니다. 설명을 위해 3xN 크기의 타일을 채우는 경우의 수를 dp[N]이라고 하겠습니다. dp[N]을 구하기 위해서는 기본적으로 dp[N-2]을 사용할 수 있습니다. dp[N-2]까지 채운 다음에 dp[2]을 채우는 가짓수만큼, 즉 3*dp[N-2]가지 만큼 채울 수 있습니다. 그리고 우리는 모든 짝수 개의 줄을 사용하면 블럭을 더 채울 수 있습니다. 예를 들어 아래 3x12의 벽을 채우는 타일을 보세요.

3x12의 벽을 채우는 방법

여기서 왼쪽에서 3번째 줄부터 6번째 줄까지 하나의 세트로 사용된 걸 볼 수 있습니다. 그리고 가장 오른쪽에 위치한 타일 또한 하나의 세트로 만들어진 걸 확인할 수 있습니다. 이렇게 짝수 개의 줄을 사용하면 2가지 방법씩 더 많이 만들 수 있습니다.  아래 그림을 참고해보세요.

따라서, 우리는 dp[N]을 구하기 위해서는 dp[N-4]부터 dp[0]까지 모든 경우의 수를 2번 더해주어야 합니다. 이는 4개의 줄부터 N개의 줄까지 모든 줄을 사용해서 만들 수 있는 가짓수가 총 2가지 있기 때문입니다. 그럼 dp[N]을 구하는 점화식을 살펴봅시다.

dp[N] = dp[N-2]*3 + (dp[N-4]*2 + dp[N-6]*2 + ... + dp[0]*2)

 

만약 N의 크기가 그리 크지 않았다면 단순 반복문을 사용한 알고리즘으로 충분히 해결할 수 있습니다. 코드업 사이트에는 이 문제와 동일하지만 범위가 작은 문제(https://codeup.kr/problem.php?id=3721)가 있으니 연습 겸 풀어보세요. 아쉽게도 백준에 있는 이 문제는 N이 최대 10¹⁸이기 때문에 알고리즘을 O(logN)까지 줄여야 합니다. 이렇게 큰 숫자가 들어올 때에는 점화식을 행렬로 만들면 됩니다.

 

행렬로 표현하기 위해서는 dp[N]을 dp[N-2]와 dp[N-4]을 사용한 수식으로 바꿔야 합니다. 다행히 이 문제에서는 직관적으로 나와있어 쉽게 구할 수 있습니다. dp[N]과 dp[N-2]를 빼면 수식이 쉽게 보입니다.

dp[N] - dp[N-2] = (dp[N-2]*3 + (dp[N-4]*2 + ... +dp[0]*2)) - (dp[N-4]*3 + (dp[N-6]*2 + ... + dp[0]*2))

dp[N] - dp[N-2] = dp[N-2]*3 - dp[N-4]

dp[N] = dp[N-2]*4 - dp[N-4]

 

dp[N]을 dp[N-2]와 dp[N-4]로 나타냈으면, 계수를 사용해서 점화식을 다음과 같이 만들 수 있습니다.

이렇게 행렬을 만들었으면 남은 일은 간단합니다. dp[N]을 구하기 위해서는 우리가 구한 행렬식을 (N/2 - 1)번 곱하면 되며, 이는 분할정복 알고리즘을 활용하면 O(logN)만에 구할 수 있습니다. 그럼 문제를 해결하는 소스코드를 한번 확인해봅시다.

 

소스코드

#include <stdio.h>
#define lint long long int
#define MOD 1000000007
 
struct Matrix {
    lint m[2][2];
};
 
lint N;
Matrix M, ret;
 
Matrix mul(Matrix A, Matrix B) {
    Matrix ret;
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            ret.m[i][j] = 0;
            for(int k=0;k<2;k++) {
                ret.m[i][j] = (ret.m[i][j] + (A.m[i][k]*B.m[k][j])%MOD + MOD)%MOD;
            }
        }
    }
 
    return ret;
}
 
Matrix pow(lint k, Matrix x) {
    if(k == 1) return x;
    else {
        if(k%2 == 0) return pow(k/2, mul(x, x));
        else return mul(pow(k/2, mul(x, x)), x);
    }
}
 
int main() {
    scanf("%lld", &N);
 
    if(N%2 == 1) printf("0");
    else if(N == 2) printf("3");
    else {
        // dp[k] - dp[k-2] = 3*dp[k-2] - dp[k-4]
        // dp[k] = 4*dp[k-2] - dp[k-4]
        M.m[0][0] = 4; M.m[0][1] = -1;
        M.m[1][0] = 1; M.m[1][1] = 0;
 
        ret = pow(N/2-1, M);
        printf("%lld", (ret.m[0][0]*3 + ret.m[0][1] + MOD)%MOD);
    }
}

후기

행렬식을 찾는데 시간이 조금 걸렸던 문제입니다. 점화식을 행렬로 표현하여 거듭 제곱하는 동적 프로그래밍을 연습하기에 적절한 문제라고 생각합니다. 비슷한 문제로는 koistdy의 사회적 거리두기(http://koistudy.net/?mid=prob_page&NO=2740&SEARCH=0)문제가 있습니다. 연습을 원한다면 한번 풀어보길 추천합니다.