[백준] 12850번 본대 산책2

문제 설명

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

문제 풀이

• BruteForce나 DP로 풀기에는 D의 최대값이 10억이기 때문에 불가하다.
• 문제를 풀기 위해서는 아래와 같은 인사이트가 필요하다.

  • 문제의 노드간의 인접행렬을 표현하면 map[a][b]는 a->b로 가는 경우의 수 이다.
  • 바로 위의 인접행렬 2개를 곱하면(인접행렬곱) map2[a][b]는 a->b로 가되 시간이 2가 걸리는 경우의 수이다.
  • 바로 위의 인접행렬 2개를 곱하면(인접행렬곱) map3[a][b]는 a->b로 가되 시간이 4가 걸리는 경우의 수이다.
  • ....

• 위처럼 인접행렬의 곱을 통해 a -> b로 가는 경우의 수를 구할 수 있는데
  이 때 효율적인 메모리 관리를 위해 다음과 같이 시간을 2의 지수 형태로 표현하여 인접행렬을 구성한다.

  • adj[0][a][b] : 시간이 2^0걸리며 a->b로 가는 경우의 수
  • adj[1][a][b] : 시간이 2^1걸리며 a->b로 가는 경우의 수
  • adj[2][a][b] : 시간이 2^2걸리며 a->b로 가는 경우의 수
  • ...

• 위와 같은 인접행렬을 바탕으로 주어진 시간 D를 이진법으로 표현하여 위 인접행렬을 모두 곱하면(결과 : result[][]) result[0][0]이 문제의 답이 된다. (시작점 -> 시작점을 D만큼 시간으로 가는 경우의 수)

소스 코드 (JAVA)

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

class Main {

    public static BufferedReader br;
    public static BufferedWriter bw;

    public static int N, MAX_EXP, MOD = 1000000007;
    public static int[][][] map;
    public static int solve() {
        // N을 이진법으로 표현
        int cur = N;
        int exp = 0;
        int remain = 0;
        int[][] tmp, tmp2;
        tmp = new int[8][8];
        tmp2 = new int[8][8];
        boolean init = false;
        while (true) {
            if (cur == 0) break;
            remain = cur % 2;
            cur = cur / 2;
            if (remain == 1) {
                //임시 배열 초기화
                if (!init) {
                    init = true;
                    for (int i = 0; i < 8; i++)
                        for (int j = 0; j < 8; j++)
                            tmp[i][j] = map[exp][i][j];
                }
                //이전 배열과 행렬곱
                else {
                    for (int i = 0; i < 8; i++) {
                        for (int j = 0; j < 8; j++) {
                            long sum = 0;
                            for (int k = 0; k < 8; k++)
                                sum = (sum + (long)tmp[i][k] * (long)map[exp][k][j]) % MOD;
                            tmp2[i][j] = (int)sum;
                        }
                    }
                    for (int i = 0; i < 8; i++)
                        for (int j = 0; j < 8; j++)
                            tmp[i][j] = tmp2[i][j];
                }
            }
            exp++;
        }
        return tmp[0][0];
    }

    public static void input() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        //인접행렬 크기 구하기
        int cur = N;
        MAX_EXP = 0;
        while(true) {
            if (cur == 1) break;
            MAX_EXP++;
            cur /= 2;
        }
        //인접행렬 초기화
        map = new int[MAX_EXP + 1][8][8];
        map[0] = new int[][]{
                {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}
        };
        for (int i = 1; i < MAX_EXP + 1; i++) {
            for (int a = 0; a < 8; a++) {
                for (int b = 0; b < 8; b++) {
                    long sum = 0;
                    for (int c = 0; c < 8; c++)
                        sum = (sum + (long)map[i-1][a][c] * (long)map[i-1][c][b]) % MOD;
                    map[i][a][b] = (int)sum;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        bw.write(solve() + "\n");
        bw.flush();
    }
}