[BOJ] 12850 - 본대 산책2

https://www.acmicpc.net/problem/12850

BOJ - 본대 산책2

문제 유형: 분할 정복, 그래프, 최단거리, 다이나믹 프로그래밍

문제 난이도: Platinum V

시간 제한: 1초

메모리 제한: 512MB

 

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

나이브한 DP로는 시간 초과가 나온다.. 찾아보니 인접행렬의 거듭제곱에는 비밀이 있었다고 한다.

https://www.youtube.com/watch?v=fKpQP_g2FIs

 

우선, 그림을 기반으로 인접행렬을 직접 만들어줬다.

정보과학관을 0, 전산관을 1, 미래관을 1, 신양관을 3, 진리관을 4, 한경직기념관을 5, 학생회관을 6, 형남공학관을 7번으로 가정하고 인접행렬을 만들어줬다.

 

인접행렬을 k번 거듭제곱한 행렬 adj^k[i][j]는 i부터 j까지 k번의 이동으로 가는 경우의 수이다.

점화식은 다음과 같다:

즉, n-1번의 이동으로 i에서 k까지 이동한 경우의 수에서 k에서 j로 가는 간선이 있다면 경우의 수가 누적될 수 있는 것이다.

 

N번 거듭제곱 행렬은 N이:

짝수인 경우 N/2번 거듭제곱된 행렬의 곱으로 만들어지거나

홀수인 경우 N-1거듭제곱과 원본 행렬의 곱으로 만들어질 수 있다.

 

즉, 최종적으로 입력된 d번 거듭제곱된 행렬에서 

은 d의 거리로 0에서 출발해서 0에서 도착하는 경우의 수가 누적되어 있다. 이 값을 출력하자.

 

 

코드

C++

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

const int MOD = 1e9 + 7;

vector<vector<ll>> adj = {{0, 1, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 0},
                          {1, 1, 0, 1, 0, 1, 0, 0}, {0, 1, 1, 0, 1, 1, 0, 0},
                          {0, 0, 0, 1, 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<ll>> matMul(vector<vector<ll>> a, vector<vector<ll>> b) {
  vector<vector<ll>> c(8, vector<ll>(8, 0));
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
      for (int k = 0; k < 8; k++) {
        c[i][j] += a[i][k] * b[k][j];
      }
      c[i][j] %= MOD;
    }
  }
  return c;
}

vector<vector<ll>> solve(int d) {
  if (d == 1)
    return adj;

  if (d % 2 == 0) {
    auto x = solve(d / 2);
    return matMul(x, x);
  }

  return matMul(solve(d - 1), adj);
}

int main(int argc, char *argv[]) {
  int d;
  cin >> d;

  auto res = solve(d);
  cout << res[0][0] << "\n";

  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD int64 = 1e9 + 7

var adj [][]int64 = [][]int64{
	{0, 1, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 0},
	{1, 1, 0, 1, 0, 1, 0, 0}, {0, 1, 1, 0, 1, 1, 0, 0},
	{0, 0, 0, 1, 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},
}

func matMul(a, b [][]int64) [][]int64 {
	c := make([][]int64, 8)

	for i := 0; i < 8; i++ {
		c[i] = make([]int64, 8)
	}

	for i := 0; i < 8; i++ {
		for j := 0; j < 8; j++ {
			for k := 0; k < 8; k++ {
				c[i][j] += a[i][k] * b[k][j]
			}
			c[i][j] %= MOD
		}
	}

	return c
}

func solve(d int32) [][]int64 {
	if d == 1 {
		return adj
	}

	if d%2 == 0 {
		x := solve(d / 2)
		return matMul(x, x)
	}

	return matMul(solve(d-1), adj)
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var d int32
	fmt.Fscan(reader, &d)

	res := solve(d)

	fmt.Fprintln(writer, res[0][0])
}