백준 12850 [본대 산책2]

문제

숭실 대학교 정보 과학관은 유배를 당해서  캠퍼스의 길 건너편에 있다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 꽃 이 활짝 핀 본 대를 선망한다. 어느 날 준영이는 본 대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.

(편의 상 문제에서는 위 건물만 등장한다고 가정하자)

한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.

입력

D 가 주어진다 (1 ≤ D ≤ 1,000,000,000) 

출력

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.

---

본대 산책2의 입력값 D가 1 <= D <= 100,000 범위로 주어진 문제가 본대 산책 문제인데 이 문제의 경우엔 D의 범위가 적기 때문에 DP로 풀 수 있었다. 하지만 본대 산책2의 D값의 범위는 너무 크기 때문에 O(N)의 시간복잡도 만으로도 시간 초과가 발생한다. 따라서 우리는 이 문제를 풀기위해 인접행렬의 거듭 제곱에 대해 알아야 한다.

 

만약 다음과 같은 그래프가 있다고 할 때 인접 행렬은 다음과 같다.

출처 : https://cloudstudying.kr/lectures/371

 

i \ j	A	B	C	D
A	0	1	1	0
B	1	0	0	0
C	1	0	0	1
D	0	0	1	0

이 행렬을 H라고 하면 H[i][j] = 1번 움직여서 i에서 j까지 가는 경우의 수를 나타낸다.

 

이를 제곱하면 어떻게 될까?

 

i \ j	A	B	C	D
A	2	0	0	1
B	0	1	1	0
C	0	1	2	0
D	1	0	0	1

H^2은 다음과 같이 되고 H^2[i][j] = 2번 움직여서 i에서 j까지 가는 경우의 수를 나타낸다.

H^2가 어떻게 2번 움직여서 i에서 j까지 가는 경우의 수를 나타낼 수 있는가 의문을 가질 수 있다. 그러면 H^2를 계산하는 과정을 보고 왜 이렇게 되는지 알아보자.

 

H^2[0][0]을 구해보면 다음과 같다.

H^2[0][0] = (H[0][0] * H[0][0]) + (H[0][1] * H[1][0]) + (H[0][2] * H[2][0]) + (H[0][3] * H[3][0])  

H^2[0][0] = (1번 움직여서 0 -> 0으로 가는 경우의 수 * 1번 움직여서 0 -> 0으로 가는 경우의 수)

                     + (1번 움직여서 0 -> 1로 가는 경우의 수 * 1번 움직여서 1 -> 0으로 가는 경우의 수) 

                     + (1번 움직여서 0 -> 2로 가는 경우의 수 * 1번 움직여서 2 -> 0으로 가는 경우의 수) 

                     + (1번 움직여서 0 -> 3으로 가는 경우의 수 * 1번 움직여서 3 -> 0으로 가는 경우의 수) 

H^2[0][0] = (2번 움직여서 0 -> 0 -> 0으로 가는 경우의 수)

                     + (2번 움직여서 0 -> 1 -> 0으로 가는 경우의 수)

                     + (2번 움직여서 0 -> 2 -> 0으로 가는 경우의 수)

                     + (2번 움직여서 0 -> 3 -> 0으로 가는 경우의 수)

 

∴ H^2[0][0] = 2번 움직여서 0에서 0으로 가는 경우의 수가 되는 것을 알 수 있다.

 

이렇게 주어진 N을 분할 정복하며 H를 거듭제곱한 행렬이 L이라 할 때 L[0][0]의 값이 이 문제의 답이라 할 수 있다.

(물론 행렬을 제곱하는 과정에서 문제의 조건대로 % 1,000,000,007을 계속 해줘야한다)

 

코드는 다음과 같다.

 

import java.io.*;
import java.util.*;
public class Main {
    static long mod = 1000000007;
    static long[][] square(long[][] arr1, long[][] arr2){
        long[][] new_arr = new long[8][8];
        for (int i = 0; i < 8; i++){
            for (int j = 0; j < 8; j++){
                for (int k = 0; k < 8; k++){
                    new_arr[i][j] =(new_arr[i][j] + (arr1[i][k] * arr2[k][j]) % mod) % mod;
                }
            }
        }
        return new_arr;
    }
    static long[][] divide(long[][] arr, long N){
        if (N == 1) return arr;
        if (N % 2 == 0){
            long[][] arr1 = divide(arr, N / 2);
            return square(arr1, arr1);
        }
        else
            return square(divide(arr, N - 1), arr);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());
        long[][] arr = new long[8][8];
        arr[0][1] = arr[0][7] = arr[1][0] = arr[1][7] = arr[1][2] = arr[2][1] = 1;
        arr[2][7] = arr[2][6] = arr[2][3] = arr[3][2] = arr[3][6] = arr[3][4] = 1;
        arr[4][3] = arr[4][5] = arr[5][4] = arr[5][6] = arr[6][2] = arr[6][3] = 1;
        arr[6][5] = arr[6][7] = arr[7][0] = arr[7][1] = arr[7][2] = arr[7][6] = 1;
        arr = divide(arr, N);
        System.out.println(arr[0][0]);
    }
}