[백준 12850] 본대 산책2

 

 

 수학과 분할 정복을 이용하는 문제. D의 크기가 최대 1,000,000,000이기 때문에 O(n)인 DP로 해결하려고 해도 시간초과가 날 것이다. 그래서 다른 방법을 생각해보아야 한다.

 

 먼저 특정 건물 i에서 특정 건물 j로 이동하는 경로 수를 matrix[i][j]에 저장하겠다고 생각했다. 이걸 1분을 소모했을 때를 기준으로 만들게 되면 이는 인접 행렬이 된다. 그렇다면 2분을 소모해서 특정 건물 i에서 i로 돌아오는 방법은 어떻게 구할 수 있을까를 생각해보았다. 이는 가능한 모든 j에 대해, 1분에 걸쳐 건물 i에서 j로 이동하는 경로 수 * 1분에 걸쳐 건물 j에서 i로 이동하는 경로 수를 모두 합친 것으로 생각할 수 있다.

 가만히 보고 있으면 알 수 있듯이, 이는 행렬 곱 형태이다. 이후의 n분에 대해서 확장해도 이는 matrix를 n제곱 한 형태로 나타나게 된다. 따라서 인접 행렬을 n제곱해서 정보과학관에서 출발해 정보과학관에 도착하는 경우의 수를 나타내는 값을 가져와 답을 구할 수 있다. 

 

 하지만 여기서 D의 크기가 매우 크기 때문에, 이를 행렬 곱을 한번씩 반복하며 구할 순 없고 분할 정복을 사용해서 구해준다. 그러면 선형 시간에서 로그 시간에 해당하는 복잡도로 바뀌기 때문에 시간 초과 문제는 해결된다.

 

 문제를 인접 행렬의 거듭 제곱꼴로 치환해서 푸는 발상이 어려웠던 문제였다. 이런 문제를 볼 때마다 선형 대수학을 가까이 하고 살아야겠다는 생각이 든다..

 

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

vector<vector<long long> > squareMatrix(vector<vector<long long> >& mat1, vector<vector<long long> >& mat2) {
    vector<vector<long long> > newMatrix(8, vector<long long>(8, 0));

    for(int i=0; i<8; i++) {
        for(int j=0; j<8; j++) {
            for(int k=0; k<8; k++) {
                newMatrix[i][j] = (newMatrix[i][j] + (mat1[i][k] * mat2[k][j]) % MOD) % MOD;
            }
        }
    }

    return newMatrix;
}

vector<vector<long long> > power(int n, vector<vector<long long> >& mat) {
    if(n==1) return mat;

    vector<vector<long long> > dividedMatrix = power(n/2, mat);
    vector<vector<long long> > newMatrix = squareMatrix(dividedMatrix, dividedMatrix);
    if(n%2==0) {
        return newMatrix;
    }else {
        return squareMatrix(newMatrix, mat);
    }
}

int main() {
    int d;
    cin >> d;

    //{ 정보과학관, 전산관, 신양관, 미래관, 진리관, 한경직기념관, 학생회관, 형남공학관 }
    vector<vector<long long> > adjMatrix = {
        { 0, 1, 0, 1, 0, 0, 0, 0 },
        { 1, 0, 1, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 1, 1, 1, 0, 0 },
        { 1, 1, 1, 0, 0, 1, 0, 0 },
        { 0, 0, 1, 0, 0, 1, 1, 0 },
        { 0, 0, 1, 1, 1, 0, 0, 1 },
        { 0, 0, 0, 0, 1, 0, 0, 1 },
        { 0, 0, 0, 0, 0, 1, 1, 0 },
    };

    vector<vector<long long> > result = power(d, adjMatrix);
    cout << result[0][0];
}