[백준 10830번] 행렬 제곱 - JAVA

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

10830번: 행렬 제곱

풀이

사용한 알고리즘 : 분할정복

 

풀이전략

밑이 C, 지수가 n인 수가 있을 때, C^n을 효과적으로 구하기 위해서는 분할 정복 알고리즘이 사용된다.

 

분할 정복 알고리즘을 사용하지 않고 C를 n번 곱하게 되면

시간 복잡도가 O(n)이 된다.

 

그런데 위 문제에서 지수로 쓰이는 B의 범위가 1<=B<=10,000,000,000로 주어졌다.

코딩테스트에서 JAVA는 보통 1초에 1억번 연산이 가능한데,

B의 최대 범위가 10억으로 약 10초 이상이 소요된다.

 

하지만 해당 문제의 시간 제한은 1초로,

만약 C를 n 번 곱하여 C^n을 계산하는 경우 시간 초과가 발생할 수 있다.

 

따라서 이전에 말한 분할 정복 알고리즘을 사용하여 이를 해결해야 한다.

위 수식은 분할 정복 알고리즘에서 사용되는 기본적인 식이다.

C^a*C^b = C^(a+b) 이기 때문에 위 수식이 성립한다.

 

만약 n=16인경우

C^16 = C^8*C^8

C^8= C^4*C^4

C^4= C^2*C^2

C^2=C^1*C^1

C^1=C

 

로 총 log(16)+1=4+1번의 연산이 수행된다.

따라서 시간 복잡도가 O(logn)으로, 이전 반복문을 통한 연산보다 훨씬 빠르게 값을 구할 수 있게된다.

 

근데 우리가 제곱해야할 수인 밑이 행렬로 주어졌기 때문에 행렬의 곱연산이

어떻게 수행되는지 알아야 한다.

그리고 위의 방법을 이를 삼중 반복문을 사용해서 코드로 나타내면 아래와 같다.

for(int l=0;l<N;++l){
    for(int n=0;n<N;++n){
        for(int m=0;m<N;++m){
           AB[l][n]+=(A[l][m]*B[m][n]);
        }
    }
}

 

제출코드

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

public class Main {

    static int N;
    static long matrix[][];

    static long[][] fpow(long matrix[][], long squareNum){
        if(squareNum==1) return matrix;
        else{
            long x[][] = fpow(matrix,(long)(squareNum/2L));

            long evenResultMatrix[][] = new long[N][N];
            for(int i=0;i<N;++i){
                for(int j=0;j<N;++j){
                    for(int k=0;k<N;++k){
                        evenResultMatrix[i][j]+=(x[i][k]*x[k][j]);
                    }
                    evenResultMatrix[i][j]%=1000L;
                }
            }
            if(squareNum%2==0){
                return evenResultMatrix;
            }
            else{
                long oddResultMatrix[][] = new long[N][N];
                for(int i=0;i<N;++i){
                    for(int j=0;j<N;++j){
                        for(int k=0;k<N;++k){
                            oddResultMatrix[i][j]+=(evenResultMatrix[i][k]*matrix[k][j]);
                        }
                        oddResultMatrix[i][j]%=1000L;
                    }
                }
                return oddResultMatrix;
            }
        }
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        matrix=new long[N][N];

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;++j){
                matrix[i][j]=Long.parseLong(st.nextToken())%1000;
            }
        }

        long resultMatrix[][] = fpow(matrix,B);

        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                bw.write(resultMatrix[i][j]+" ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
}