[백준] 12850: 본대 산책2 - JAVA

in Algorithm on 수학

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

풀이

결론부터 말하면 분할정복을 통해 행렬의 거듭제곱을 하는 문제였다.

각각의 포인트에서 연결된 길을 이차원배열에 저장했다.

초기 배열을 V1이라고 하면 V1[a][b]는 a에서 b로 1분만에 갈 수 있는 경로의 수를 의미한다.

V1을 제곱한 것을 V2라고 하면 V2[a][b]는 a에서 b로 2분만에 갈 수 있는 경우의 수이다.

즉, Vx[a][b]는 a에서 b로 x분만에 갈 수 있는 경우의 수를 의미한다.

따라서 주어진 D만큼 V행렬을 제곱하여 V[0][0]을 구하면 D분만에 0에서 0으로 갈 수 있는 경우의 수이다.

분할정복은 doPow함수로 구현했고, 행렬의 곱셈은 multiply함수로 구현했다.

메모리: 14256KB

시간: 124ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static long[][] v = {
            { 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 }
    };

    final static long MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int D = Integer.parseInt(br.readLine());

        long[][] ans = doPow(D);

        System.out.println(ans[0][0]);
    }

    private static long[][] doPow(int n) {
        if (n == 1) {
            return v;
        }

        long[][] tmp = doPow(n / 2);
        tmp = multyply(tmp, tmp);
        if (n % 2 == 1) {
            tmp = multyply(tmp, v);
        }

        return tmp;
    }

    private static long[][] multyply(long[][] a, long[][] b) {
        long[][] tmp = 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++) {
                    tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }

        return tmp;
    }

}