BOJ 12850(본대 산책2) 풀이

이미지를 누르면 문제로 이동합니다

 

이 문제는 "정보과학관"이라는 곳에서 출발해서 D번째에 다시 "정보과학관"에 있을 경우의 수를 구하는 문제다.

D가 작다면 DP 를 이용해 풀어주면 되지만, 이 문제는 D가 10억까지 제공된다.

 

그럼 어떻게 풀 수 있을까?

 

우리는 여기서 모든 정점 간의 거리가 같음을 이용해야 한다.

 

위 그림은 문제에서 제공된 그림이고, 숫자는 각 정점에 부여해준 번호이다.

 

이제 위 그래프를 가지고 DP를 생각해 보자.

 

DP [n][d] : n까지 오는데, d만큼 소요될 때 경우의 수

 

라고  DP를 정의할 수 있다. 그리고 n이 작으니 각 정점별로 DP 식을 정리해 보자.

 

DP [1][d] = DP [2][d-1] + DP [3][d-1]

DP [2][d] = DP [1][d-1] + DP [3][d-1] + DP [4][d-1]

DP [3][d] = DP [1][d-1] + DP [2][d-1] + DP [4][d-1] + DP [5][d-1]

Dp [4][d] = DP [2][d-1] + DP [3][d-1] + DP [5][d-1] + DP [6][d-1]

DP [5][d] = DP [3][d-1] + DP [4][d-1] + DP [6][d-1] + DP [8][d-1]

DP [6][d] = DP [4][d-1] + DP [5][d-1] + DP [7][d-1]

DP [7][d] = DP [6][d-1] + DP [8][d-1]

DP [8][d] = DP [5][d-1] + DP [7][d-1]

 

이 된다. 여기서 DP 식을 잘 보면, 모두 d-1을 알고 있다면 d일 때를 구할 수 있게 된다.

즉, D에 대해 각각의 정점에서 경우의 수는 D-1을 통해 구할 수 있다는 말이다.

 

이때, 우리는 피보나치를 행렬로 계산하는 방법을 생각해 보자.

 

피보나치는 위와 같은 방식으로 구할 수 있다. 

임의의 n에 대한 피보나치를 구하고 싶다면, 맨 처음 행렬을 계속 앞에서 곱해주면 된다.

위와 같이 해주면 임의의 n에 대한 피보나치를 구할 수 있다.

 

이 문제도 이와 같은 방법을 적용해 주면 된다.

\begin{equation} \begin{pmatrix} 0&1&1&0&0&0&0&0\\ 1&0&1&1&0&0&0&0\\ 1&1&0&1&1&0&0&0\\ 0&1&1&0&1&1&0&0\\ 0&0&1&1&0&1&0&1\\ 0&0&0&1&1&0&1&0\\ 0&0&0&0&0&1&0&1\\ \end{pmatrix}^d × \begin{pmatrix} dp[1][0] \\ dp[2][0] \\ ... \\ dp[7][0] \\ dp[8][0] \end{pmatrix} = \begin{pmatrix} dp[1][d] \\ dp[2][d] \\ ... \\ dp[7][d] \\ dp[8][d] \end{pmatrix} \end{equation}

 

이제 행렬곱을 d번 해주면 된다.

당연하게도 O(d)로 계산해 주면 시간초과가 발생하니, 여기서 분할정복을 이용한 거듭제곱을 이용해 준다.

 

어떤 수 A에 대해 A의 2n승은 다음과 같이 작성할 수 있다.

\begin{equation} A^{2n} = A^n * A^n \end{equation}

 

즉, A^n을 한번 구했다면, 다음번은 구하지 않아도 된다. 이를 이용하면 N번 걸리는 과정을 log(N)에 처리할 수 있게 된다.

 

l=[[0,1,1,0,0,0,0,0],
	[1,0,1,1,0,0,0,0],
	[1,1,0,1,1,0,0,0],
    [0,1,1,0,1,1,0,0],
	[0,0,1,1,0,1,0,1],
	[0,0,0,1,1,0,1,0],
	[0,0,0,0,0,1,0,1],
	[0,0,0,0,1,0,1,0]]

mod = int(1e9+7)
d = int(input())
def conv(A,B):
    r = [[0 for i in range(8)]for g in range(8)]
    for i in range(8):
        for g in range(8):
            v=0
            for k in range(8):
                v+=A[i][k]*B[k][g]
                v%=mod
            r[i][g] = v
    return r
        
def func(x):
    if x==0:
        return [[0 for i in range(8)]for g in range(8)]
    if x==1:
        return l    
    T = func(x//2)
    if x%2==0:
        return conv(T,T)
    else:
        return conv(conv(T,T),l)
    

R = func(d-1)
#print(R)
print((R[0][1]+R[0][2])%mod)