백준 13976 타일 채우기 2 : 파이썬

• 문제 링크 : 타일 채우기 2

3xN의 타일을 2x1과 1x2타일로 채우는 문제입니다.

이 문제의 점화식 유도까지 아래 링크에 설명이 되어있으므로 참고하시면 됩니다.

• 타일채우기

하지만 위의 방법대로 하게되면 시간초과가 납니다. 위와 같이 O(N)방식으로의 탐색은 입력크기가 $10^{18}$인 것을 생각하면 제한시간 내 탐색할 수 없기 때문이죠. 따라서 O(logN)의 시간복잡도를 가지는 방식을 떠올려 보아야 하겟습니다.

그래서 아래와 같이 기존 점화식을 여러 방면으로 변환을 해보았습니다.

• $n$이 짝수일 때 아래와 같이 생각해볼 수 있습니다.
  $\begin{aligned} a_n &= 3\times a_{n-2} + 2\times a_{n-4} + ... + 2\times a_{2} + 2 \times a_0 \\ a_{n-2} &= 3\times a_{n-4} + 2\times a_{n-6} + ... + 2\times a_{2} + 2 \times a_0\\ &= a_{n-4} + 2 \times(a_{n-4}+a_{n-6}+...+a_2+a_0) \\ a_{n-2}- a_{n-4}&=2 \times(a_{n-4}+a_{n-6}+...+a_2+a_0) \end{aligned} \\ \therefore a_{n} = 4 \times a_{n-2} - a_{n-4}$

이 때, $a_0$는 일관되게 점화식으로 표기되게 끔 하기위해 표기하였습니다. ($a_0$ = 1)

이를 행렬을 활용한 형태로 표현하려면, 아래 조건을 만족하는 행렬 $A$를 구하면 됩니다. 다만 점화식의 시작이 $a_2$을 고려해서 점화식을 수정하겟습니다.
$a_{n+2} = 4 \times a_{n} - a_{n-2}$를 기준으로 만들어진 조건식입니다.

• $\begin{pmatrix} a_{n+2} \\ a_{n} \end{pmatrix} = A\begin{pmatrix} a_{n} \\ a_{n-2} \end{pmatrix} (n=2,4, ...)$

$a_n$에 대한 점화식을 참고하면, 아래와 같은 식을 구할 수 있습니다.

$\begin{pmatrix} a_{n+2} \\ a_{n} \end{pmatrix} = \begin{pmatrix} 4&-1 \\ 1&0 \end{pmatrix} \cdot \begin{pmatrix} a_{n} \\ a_{n-2} \end{pmatrix}$

그리고 방금 구한 식을 반복해 나가면 행렬의 $n$제곱 형태의 식을 얻을 수 있게 됩니다.

$\begin{pmatrix} a_{n+2} \\ a_{n} \end{pmatrix} = \begin{pmatrix} 4&-1 \\ 1&0 \end{pmatrix}^{\frac{n}{2}} \cdot \begin{pmatrix} a_{2} \\ a_{0} \end{pmatrix}$

따라서 최종식은 아래와 같이 유도가 되었습니다.

$\begin{pmatrix} a_{n+2} \\ a_{n} \end{pmatrix} = \begin{pmatrix} 4&-1 \\ 1&0 \end{pmatrix}^{\frac{n}{2}} \cdot \begin{pmatrix} 3 \\ 1 \end{pmatrix} (\because a_2=3, a_0=1)$

즉, 행렬의 N제곱을 구하는 문제로 바뀐 것을 볼 수 있었습니다.
이는 $n$에 대해 재귀적 방식으로 $\frac{n}{2}$로 나누어 나간 후, 최소단위인 1일 때부터 곱해나가는 방식으로 합치는 divide & conquer방식으로 접근할 수 있었습니다.

아래 문제도 풀어보시면 문제해결에 도움이 될 수 있을거 같습니다.

• 행렬 제곱

행렬에 음수가 포함되어 있지만, 위 문제처럼 행렬 원소가 모두 양수일 때처럼 모듈러 연산을 해주어도 동일한 결과를 얻을 수 있었습니다.

pow_matrix()은 n제곱 행렬에 대해 절반의 크기로 divide하는 함수이고, mul_matrix()로 두 행렬에 대한 곱한 결과의 행렬을 return해주며 나눈 결과를 합쳐나가는데 활용했던 함수입니다.

## method
def pow_matrix(n): # n : 지수승 / return -> matrix
    
    if n == 1 : return [[4,-1],[1,0]]
    elif n == 0 : return [[1,0],[0,0]]
    else :
        half = pow_matrix(n >> 1)
        if n%2 :
            return mul_matrix(mul_matrix(half,half),pow_matrix(1))
        else :
            return mul_matrix(half,half)
        
def mul_matrix(m1,m2): 
    global MOD
    res = [[0]*2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                res[i][j] += ((m1[i][k] * m2[k][j]))
            res[i][j] %= MOD
    return res
## input
from collections import defaultdict
N = int(input())
MOD = int(1e9+7)

## output
if N%2 == 1: print(0)
else:
    sub = [[3,0],[1,0]] # (dp1,dp0 )

    result = pow_matrix(N//2-1)
    # 마지막에 열벡터 (3,1)을 곱할 때 모듈러 연산이 실행되지 않음.
    answer = mul_matrix(result,sub)

    print(answer[0][0])

다만 저로서는 마지막에 $\begin{pmatrix} 3 \\ 1 \end{pmatrix}$을 곱해준 후에 모듈러 연산을 안해줘서 원하는 값대로 안 나왔던 실수를 했었습니다.

따라서 마지막에도 마찬가지로 모듈러 연산 처리를 하여 원하는 출력을 얻어낼 수 있었습니다.