백준 12850 (C++) 본대 산책2

최초 업로드: 2025-08-01 16:17:16

최근 수정 시간: 2025-08-01 16:30:32

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 본대 산책2

[문제 링크](https://www.acmicpc.net/problem/12850)

## 문제 설명

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

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

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

## 입력

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

## 출력

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

## 풀이
#### 각각의 건물을 하나의 노드로, 연결된 도로를 하나의 간선으로 두고 풀었다.
#### D가 최대 $10^9$까지여서 그냥 dp로는 시간초과가 발생한다.
#### 이를 분할정복으로 행렬 거듭제곱을 하여 빠르게 계산하였다.
#### 이는 마르코프 체인에서 k스텝 후 상태 확률을 계산하는 문제와 유사한 방법이다.

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

const long long MOD = 1e9+7;

long long conn[8][8] = {
    {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, 1, 0},
    {0, 0, 0, 1, 1, 0, 0, 1},
    {0, 0, 0, 0, 1, 0, 0, 1},
    {0, 0, 0, 0, 0, 1, 1, 0},
};

long long dp[8][8] = { // dp[i][j] : i에서 j로 가는 경우의 수
    {1, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 0},
    {0, 0, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 1},
};

void matrix_square() {
 long long nextConn[8][8] = {0, };
 for(int i=0;i<8;i++) {
 for(int j=0;j<8;j++) {
 for(int k=0;k<8;k++) {
 nextConn[i][j] += conn[i][k] * conn[k][j];
 }
 nextConn[i][j] %= MOD;
 }
 }
 memcpy(conn, nextConn, sizeof conn);
}

void matrix_mult() {
 long long nextDp[8][8] = {0, };
 for(int i=0;i<8;i++) {
 for(int j=0;j<8;j++) {
 for(int k=0;k<8;k++) {
 nextDp[i][j] += dp[i][k] * conn[k][j];
 }
 nextDp[i][j] %= MOD;
 }
 }
 memcpy(dp, nextDp, sizeof dp);
}

void expo_pow(long long n) {
    if(n==0) return;
    if(n%2) matrix_mult();
    matrix_square();
    expo_pow(n>>1);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 long long n; cin >> n;
 expo_pow(n);
 cout << dp[0][0];
}
```