[백준 12850] 본대 산책2 / 자바 / 수학

#문제         

레벨: G1
알고리즘: 수학
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

N의 최대값이 1억이다. 이미 브루트포스는 실패이다. 그렇다 하면 종료조건을 걸얼 백트래킹하게 하는 건 어떨까? 백트래킹의 조건은 학생회관까지 갔는데 남은 시간이 3분인 거다. 돌아가는 시간은 최소 4분이 걸리기 때문에 이미 실패다. 이 뒤에 상황을 안 살펴봐도 되는 거다.

아니다. 그렇다 하더라도 무조건 시간복잡도에서 걸릴 것이다. 생각이 나지 않는다. 그래서 다른 사람의 풀이를 참조하였다. 

문제의 포인트는 행렬곱셈이다.

 

예를 들어 설명하겠다.  아래 표는 1초에 i에서 j까지 갈 수 있는 경우의 수 배열이다.

N =1	A	B	C
A	0	1	1
B	1	0	1
C	1	1	0

 

만약 2초에 i에서 j까지 갈 수 있는 경우의 수 배열을 만들려면 어떻게 해야 할까

 

만약 A -> A 까지 2에 갈 수 있는 경우의 수를 구하자면 

(A -> A 경우의수  X A -> A 경우의수)   + (A -> B 경우의수  X B -> A 경우의수)  + (A -> C 경우의수  X C -> A 경우의수) 일 것 아닌가.

 

위 식 자체가 행렬곱셈을 표현한 것이다. 아래는 행렬곱셈 공식인데 위 식이랑 같지 않은가?

 

그래서 위 문제는 N번의 행렬곱셈을 통해 해결할 수 있다. 

 

또 여기서! 포인트가 들어간다.

행렬곱셈의 성질을 이용하는 것이다. 곱셈의 결합 법칙을 이용하는 것이다.

행렬A x 행렬A x 행렬A x 행렬A  x 행렬A x 행렬A  x 행렬A x 행렬A 

위 식대로 행렬A의 ^8을 구하면하면 7번의 연산이 필요하다.

 

곱셈의 결합 법칙을 이용하면 A^8을 구하기 위해 A^4 x A^4을 구해야 할 것이고 A^4를 구하기 위해서는  A^2 x A^2를 구해야 할 것이고  A^2를 구하기 위해서는 A x A를 구해야 할 것이다.  총 A x A의 연산, A^2 x A^2의 연산,  A^4 x A^4 만 구하면 되기 때문에 총 3 번의 연산만 필요하다.

 

---

#풀이 코드      

import java.io.*;
import java.util.*;
public class Main {
    static long mod = 1000000007;
   
   
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());
        long[][] arr = new long[8][8];
        arr[0][1] = arr[0][7] = arr[1][0] = arr[1][7] = arr[1][2] = arr[2][1] = 1;
        arr[2][7] = arr[2][6] = arr[2][3] = arr[3][2] = arr[3][6] = arr[3][4] = 1;
        arr[4][3] = arr[4][5] = arr[5][4] = arr[5][6] = arr[6][2] = arr[6][3] = 1;
        arr[6][5] = arr[6][7] = arr[7][0] = arr[7][1] = arr[7][2] = arr[7][6] = 1;
        arr = divide(arr, N);
        System.out.println(arr[0][0]);
    }
    
    //행렬 곱셈의 결합법칙 이용하여 연산 단축
    static long[][] divide(long[][] arr, long N) {
        if (N == 1) return arr;
        if (N % 2 == 0){
            long[][] arr1 = divide(arr, N / 2);
            return square(arr1, arr1);
        }
        else
            return square(divide(arr, N - 1), arr);
    }

    //행렬 곱셈
    static long[][] square(long[][] arr1, long[][] arr2){
        long[][] new_arr = 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++){
                    new_arr[i][j] =(new_arr[i][j] + (arr1[i][k] * arr2[k][j]) % mod) % mod;
                }
            }
        }
        return new_arr;
    }
    

}