[백준] 12850 - 본대 산책 2 (Java/자바)

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

12850번: 본대 산책2

풀이 방법

어떻게 풀어야 하나 고민하다가 답이 안 나와서 바로 구글링을 했다.

입력이 10^9까지 들어와서 O(N)으로 해도 시간초과가 떠서 O(logN)으로 해결해야 했다.

 

풀이 방식을 제일 잘 설명해준게 이 블로그다.

https://chinpa.tistory.com/149

[백준] 12850 - 본대 산책 2 (G1)

행렬 거듭제곱을 사용하는 문제 자체를 처음 접해봐서 비슷한 문제들을 풀면서 외우듯이 익혀야 할 것 같다.

 

 

import java.io.*;

public class MyClass {
    static final int MOD = 1000000007;
    
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long D = Long.parseLong(br.readLine());
        // System.out.println(D);
        
        long[][] matrix = {{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}};
                              
        matrix = pow(matrix, D);
        System.out.print(matrix[0][0]);
        

        
    }   // end of main
    
    /** m1, m2 두 행렬을 곱한 결과(행렬)을 반환*/
    public static long[][] mul(long[][] m1, long[][] m2){
        long[][] res = new long[8][8];
        
        for(int i = 0 ; i < m1.length ; i++){
            for(int j = 0 ; j < m2[0].length ; j++){
                for(int k = 0 ; k < m1[0].length ; k++) {
                    res[i][j] = (res[i][j]+ m1[i][k] * m2[k][j]) % MOD;
                }
            }
        }
        
        return res;
    }   // end of mul
    
    /** m 행렬을 D번 거듭제곱*/
    public static long[][] pow(long[][] m, long D){
        if(D==1) {
            return m;
        }
        
        // 분할정복
        if(D%2==0) {
            return pow(mul(m,m), D/2);
        } else {
            return mul(m, pow(mul(m,m), D/2));
        }
    }   // end of pow
}   // end of class

오늘은 내 노트북으로 푼게 아니라서 https://www.jdoodle.com/online-java-compiler/ 여기에서 작성했다.