BOJ 17272 - 리그 오브 레전설 (Large) 링크
(2024.03.28 기준 G1)

문제

A 스킬의 시전 시간은 $1$초, B 스킬의 시전 시간은 $M$초이다. 시전 시간 동안은 다른 스킬을 사용할 수 없으며 스킬을 쓰지 않는 시간은 없어야 할 때, $N$초 동안 가능한 스킬 조합의 수 출력

알고리즘

행렬 DP

풀이

$N$의 제한을 제외하면 Small과 지문이 동일하다. 일단 점화식도 Small과 마찬가지로 $dp(i)=dp(i−1)+dp(i−M)$이 쓰인다. 그런데 $N$이 너무 크기 때문에 다른 방법을 찾아야 한다.

1차원 선형 점화식은 행렬 곱으로 나타낼 수 있다. 다음은 이 문제의 점화식을 행렬 곱으로 나타낸 것이다.

$\begin{pmatrix} dp_N \\ dp_{N-1} \\ dp_{N-2} \\ \vdots \\ dp_{N-M+1} \end{pmatrix} = \begin{pmatrix} 1 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{pmatrix} \begin{pmatrix} dp_{N-1} \\ dp_{N-2} \\ dp_{N-3} \\ \vdots \\ dp_{N-M} \end{pmatrix}$

행렬 곱을 풀어보면, $dp_N = dp_{N-1} + dp_{N-M}$, $dp_{N-1} = dp_{N-1}$, $\dots$ 식들을 얻을 수 있다.

아무튼 위 식에서 우변의 오른쪽 행렬을 재귀 느낌으로 계속 풀어주면

$\begin{pmatrix} dp_N \\ dp_{N-1} \\ dp_{N-2} \\ \vdots \\ dp_{N-M+1} \end{pmatrix} = \begin{pmatrix} 1 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{pmatrix}^N \begin{pmatrix} dp_0 \\ dp_{-1} \\ dp_{-2} \\ \vdots \\ dp_{-M+1} \end{pmatrix} = \begin{pmatrix} 1 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{pmatrix}^N \begin{pmatrix} 1 \\ 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$

위와 같이 정리할 수 있다.

결국은 우변의 왼쪽 행렬을 $N$번 제곱해서 나오는 행렬의 $0$행 $0$열 원소가 $dp_N$이 됨을 알 수 있다. 이는 단위 행렬과 분할 정복을 이용해 빠른 거듭제곱으로 풀어내면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<vector<ll>> matrix;

const ll MOD = 1'000'000'007;

// 행렬 곱
matrix mul(matrix &A, matrix &B){
    // 행렬 A와 행렬 B의 곱은 A의 열과 B의 행 수가 같아야 한다.
    // 또한 곱의 결과는 A의 행의 수와 B의 열의 수를 크기로 갖는다.
    int n = A.size(), m = B[0].size(), l = A[0].size();
    matrix res(n, vector<ll>(m));
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < l; k++)
        res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % MOD;
    return res;
}

// 빠른 거듭제곱
matrix fpow(matrix &mat, ll k){
    int M = mat.size();
    matrix res(M, vector<ll>(M));
    for (int i = 0; i < M; i++) res[i][i] = 1;
    while (k){
        if (k & 1) res = mul(res, mat);
        mat = mul(mat, mat);
        k >>= 1;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll N; int M; cin >> N >> M;

    /* i초 때 가능한 경우의 수는 두 가지가 있다.
    i-1초까지 스킬 쓴 상태에서 A 스킬 사용
    i >= M일 때, i-M초까지 스킬 쓴 상태에서 B 스킬 사용
    dp(i) = dp(i-1) + dp(i-M)
    
    N이 너무 크기 때문에 행렬 DP로 풀어내자.
    1차원 선형 점화식으로 나타낼 수 있기 때문에 행렬 DP가 가능하다.
    
    dp(N) = dp(N-1) + dp(N-M)
    dp(N-1) = dp(N-1)
    ...
    dp(N-M+1) = dp(N-M+1)
    위와 같은 M개의 항을 행렬로 표현하고 정리를 하면
    행렬의 N제곱의 0행 0열 원소임을 알 수 있다. */

    matrix mat(M, vector<ll>(M));
    mat[0][0] = mat[0][M - 1] = 1;
    for (int i = 1; i < M; i++) mat[i][i - 1] = 1;

    cout << fpow(mat, N)[0][0];
}

• Python

import sys; input = sys.stdin.readline
MOD = 1000000007

def mul(A, B):
    # 행렬 A와 행렬 B의 곱은 A의 열과 B의 행 수가 같아야 한다.
    # 또한 곱의 결과는 A의 행의 수와 B의 열의 수를 크기로 갖는다.
    n = len(A); m = len(B[0]); l = len(A[0])
    res = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(l):
                res[i][j] += A[i][k] * B[k][j]
                res[i][j] %= MOD
    return res

# 빠른 거듭제곱
def fpow(mat, k):
    res = [[0] * M for _ in range(M)]
    for i in range(M):
        res[i][i] = 1
    while k:
        if k & 1:
            res = mul(res, mat)
        mat = mul(mat, mat)
        k >>= 1
    return res

N, M = map(int, input().split())

''' i초 때 가능한 경우의 수는 두 가지가 있다.
i-1초까지 스킬 쓴 상태에서 A 스킬 사용
i >= M일 때, i-M초까지 스킬 쓴 상태에서 B 스킬 사용
dp(i) = dp(i-1) + dp(i-M)

N이 너무 크기 때문에 행렬 DP로 풀어내자.
1차원 선형 점화식으로 나타낼 수 있기 때문에 행렬 DP가 가능하다.

dp(N) = dp(N-1) + dp(N-M)
dp(N-1) = dp(N-1)
...
dp(N-M+1) = dp(N-M+1)
위와 같은 M개의 항을 행렬로 표현하고 정리를 하면
행렬의 N제곱의 0행 0열 원소임을 알 수 있다. '''

mat = [[0] * M for _ in range(M)]
mat[0][0] = mat[0][M - 1] = 1
for i in range(1, M):
    mat[i][i - 1] = 1

print(fpow(mat, N)[0][0])