[백준 12850] 본대 산책2 (C#, C++) - soo:bak

작성일 :

문제 링크

12850번 - 본대 산책2

설명

정보과학관에서 출발하여 정확히 D분 후 다시 정보과학관으로 돌아오는 경로의 수를 구하는 문제입니다. 8개의 건물이 있고, 인접한 건물로 이동하는 데 1분이 걸립니다.


접근법

먼저 건물 간 연결을 8x8 인접행렬로 나타냅니다. 이 행렬을 한 번 곱하면 1분 후 각 건물에서 각 건물로 가는 경로 수가 되고, 두 번 곱하면 2분 후 경로 수가 됩니다.

다음으로 D분 후 경로 수를 구하려면 행렬을 D번 곱해야 합니다. D가 최대 10억이므로 단순히 곱하면 시간 초과가 발생하지만, 분할 정복으로 O(log D)번만 곱해도 됩니다.

이후 결과 행렬에서 정보과학관에서 정보과학관으로 가는 경로 수, 즉 (0, 0) 원소를 출력합니다.


Code

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

using System;

namespace Solution {
  class Program {
    const long MOD = 1_000_000_007L;

    static long[,] Mul(long[,] a, long[,] b) {
      var r = new long[8, 8];
      for (var i = 0; i < 8; i++) {
        for (var k = 0; k < 8; k++) {
          if (a[i, k] == 0)
            continue;
          for (var j = 0; j < 8; j++)
            r[i, j] = (r[i, j] + a[i, k] * b[k, j]) % MOD;
        }
      }
      return r;
    }

    static long[,] Pow(long[,] baseM, long exp) {
      var res = new long[8, 8];
      for (var i = 0; i < 8; i++)
        res[i, i] = 1;
      while (exp > 0) {
        if ((exp & 1) == 1)
          res = Mul(res, baseM);
        baseM = Mul(baseM, baseM);
        exp >>= 1;
      }
      return res;
    }

    static void Main(string[] args) {
      var D = long.Parse(Console.ReadLine()!);
      long[,] adj = {
        {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}
      };

      var ans = Pow(adj, D);
      Console.WriteLine(ans[0, 0] % MOD);
    }
  }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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

typedef long long ll;
typedef array<array<ll, 8>, 8> Mat;

const ll MOD = 1'000'000'007LL;

Mat mul(const Mat& a, const Mat& b) {
  Mat r{};
  for (int i = 0; i < 8; i++) {
    for (int k = 0; k < 8; k++) {
      if (a[i][k] == 0)
        continue;
      for (int j = 0; j < 8; j++)
        r[i][j] = (r[i][j] + a[i][k] * b[k][j]) % MOD;
    }
  }
  return r;
}

Mat power(Mat base, ll exp) {
  Mat res{};
  for (int i = 0; i < 8; i++)
    res[i][i] = 1;
  while (exp > 0) {
    if (exp & 1)
      res = mul(res, base);
    base = mul(base, base);
    exp >>= 1;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll D; cin >> D;
  Mat adj {{
    {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}
  }};

  Mat ans = power(adj, D);
  cout << ans[0][0] % MOD << "\n";

  return 0;
}

이 블로그의 다른 글