10830번 - 행렬 제곱

1️⃣ 로그

 

✏️ 풀이 과정

행렬 거듭제곱을 구현하는 문제입니다. B가 천억까지 가능해서 당황하기 쉽지만 A를 제곱한 A^2을 또 제곱하는 식으로 큰 수를 구하면 A^(2^37)이 천억을 넘기 때문에 36번의 계산만으로 비슷한 수를 얻을 수 있습니다. 이러한 아이디어를 떠올렸다면 나머지는 주어진 B를 A^(2^n)들의 곱으로 나타내는 것입니다.(모든 자연수는 이진수로 변환이 가능하기 때문에 모든 경우에 이와 같이 표현할 수 있습니다.)

 

이 또한 어려워 보이지만 for문을 통해 직접 연산함으로써 간단하게 해결할 수 있습니다. log_2 계산을 취해준 이후 캐스팅을 통해 정수값을 얻고 2^(해당값)만큼을 B에서 빼주는 식으로 B가 0이 될 때까지 진행하면 어떤 n들이 해당하는 지 표시할 수 있고 이를 boolean형 배열에 저장할 수 있습니다.

 

행렬의 제곱은 3중 for문을 통해 각 행과 열에 대해서 열이 커지는 경우와 행이 커지는 경우를 곱해서 더해 구현할 수 있습니다. 제곱을 구현했다면 n 중에 가장 큰 max 값을 구하고 2^1부터 2^max까지 제곱한 값들을 저장하고 이들을 또 각각 for문을 통해 곱해줌으로써 답을 얻을 수 있습니다. 

 

⏱ 시간 복잡도

실행 횟수는 logB로 표현할 수 있고 행렬 곱셈은 O(N^3)이기 때문에 전체 시간 복잡도는 O(N^3 * logB)가 됩니다. 대략 125 * 36 정도이기 때문에 생각보다 빠르게 작동되는 것이 확인됩니다.

 

💻 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[][][] matrix;
	static int N;
	
	static void square(int n) {
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				int tmp = 0;
				for(int k=0;k<N;k++) {
					tmp += (matrix[n-1][i][k] * matrix[n-1][k][j]) % 1000;
				}
				matrix[n][i][j] = tmp % 1000;
			}
		}
	}
	
	static int[][] multiply(int[][] a, int[][] b) {
		int[][] tmparr = new int[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				int tmp = 0;
				for(int k=0;k<N;k++) {
					tmp += (a[i][k] * b[k][j]) % 1000;
				}
				tmparr[i][j] = tmp % 1000;
			}
		}
		return tmparr;
	}
	
	static int sum(int[][] mat) {
		return 0;
	}
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        int max = (int) (Math.log10(B) / Math.log10(2)) + 1;
        boolean[] check = new boolean[max]; 
        while(B > 0) {
        	int tmp = (int) (Math.log10(B) / Math.log10(2));
        	check[tmp] = true;
        	B -= Math.pow(2, tmp);
        }
        matrix = new int[max][N][N];
        for (int i = 0; i < N; i++) {
        	st = new StringTokenizer(br.readLine());
        	for (int j = 0; j < N; j++) {
				matrix[0][i][j] = Integer.parseInt(st.nextToken()) % 1000;
			}
		}
        for(int i=1;i<max;i++) {
        	square(i);
        }
        int[][] res = matrix[max-1];
        for(int i=max-2;i>=0;i--) {
        	if(check[i]) {
        		res = multiply(res, matrix[i]);
        	}
        }
        for(int i=0;i<N;i++) {
        	for(int j=0;j<N;j++) {
        		System.out.print(res[i][j]+" ");
        	}
        	System.out.println();
        }
        br.close();
    }
}