/ BOJ

BOJ_10830_행렬제곱_JAVA

문제 : 행렬 제곱

링크 : BOJ_10830_행렬제곱

접근 방식

어제 풀었던 행렬 곱셈과 오늘 먼저 풀었던 곱셈을 합쳐놓으면 딱 이 문제가 될 것 같다.

N*N 행렬의 B제곱을 구해야 하는데, B의 값의 범위가 int 값을 벗어날 정도로 매우 크다.

이 문제 역시 분할정복을 이용한 거듭제곱으로 풀어야 한다. 하지만 행렬의 곱셈은 일반적인 수의 곱셈과 다르기 때문에, 수의 곱셈 부분을 행렬의 곱셈 방식으로 바꿔주어야 한다.

행렬의 곱셈을 구하는 알고리즘과 분할정복의 거듭제곱 알고리즘을 알고 있다면 문제를 푸는 것이 그렇게 어렵지는 않을 것이다.

풀이 방법

  1. 먼저 행렬의 크기 값을 읽어들여 N*N 크기 배열을 생성하고 거듭제곱할 B 값도 읽어와 저장한 후, 배열에 값을 집어넣는다.

  2. 재귀를 통해서 분할 거듭제곱한다. 기저조건은 n이 1이 되었을 때로 한다. 행렬 크기만큼의 임시 배열을 만들어 행렬을 곱셈하는 방식으로 제곱을 먼저 시켜준다.

  3. n이 짝수라면 그대로 리턴해준다. n이 홀수라면 구한 행렬에 원본 행렬을 한 번 곱해서 리턴시켜준다.

  4. 곱셈이 이루어지는 과정중에 1000으로 나머지연산을 하는 것을 잊지 않는다.

  5. 모든 재귀가 끝난 후에 구한 행렬을 순서대로 출력한다.

소스 코드


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

public class BOJ_10830_행렬제곱 {
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		N = Integer.parseInt(st.nextToken());

		long B = Long.parseLong(st.nextToken());

		long[][] arr = new long[N][N];

		for(int i=0;i<N;i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j=0;j<N;j++) {
				arr[i][j] =  Long.parseLong(st.nextToken());
			}
		}
		long ans[][] = fpow(arr, B);

		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				System.out.print(ans[i][j]%1000 + " ");
			}
			System.out.println();
		}

	}


	static long[][] fpow(long[][] c, long n) {

		if(n == 1) {
			return c;
		}else {
			long[][] x = fpow(c, n/2);
			long[][] temp = 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++) {
						temp[i][j] += x[i][k] * x[k][j];
					}
					temp[i][j] %= 1000;
				}
			}
			if(n%2 == 0) {
				return temp;
			}else {
				long temp2[][] = 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++) {
							temp2[i][j] += temp[i][k] * c[k][j];
						}
						temp2[i][j] %= 1000;
					}
				}
				return temp2;
			}
		}

	}
}