[백준 10830] 행렬 제곱(JAVA)

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

10830번: 행렬 제곱

 

 

이 문제를 풀기전에 아래의 두 문제를 먼저 풀으시는 것을 추천드립니다!

1. 행렬 곱셈

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

2740번: 행렬 곱셈

-> 풀이 

https://iheeeee6-6.tistory.com/51

[백준 2740] 행렬 곱셈 (JAVA)

 

 

2. 곱셈

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

1629번: 곱셈

-> 풀이

https://iheeeee6-6.tistory.com/52

[백준 1629] 곱셈 (JAVA)

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

우선 이 문제는 분할 정복으로 해결할 수 있습니다.

행렬을 곱하면서 1000으로 나누고, 분할 정복을 적용하면 됩니다!

 

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

public class Main {
	static int[][] arr;
	static int n;
	static long b;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		b = Long.parseLong(st.nextToken());
		arr = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++)
				arr[i][j] = Integer.parseInt(st.nextToken())% 1000;
		}

		StringBuilder sb = new StringBuilder();
		int[][] result = pow(b);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				sb.append(result[i][j]).append(" ");
			sb.append("\n");
		}
		System.out.println(sb);
	}

	static public int[][] pow(long cnt) {
		if (cnt == 1) {
			return arr;
		}
		int[][] temp = pow(cnt / 2);
		if (cnt % 2 == 1) {
			int[][] temp2 = cal(temp, arr);
			return cal(temp, temp2);
		} else {
			return cal(temp, temp);
		}
	}

	static public int[][] cal(int[][] A, int[][] B) {
		int[][] r = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int sum = 0;
				for (int k = 0; k < n; k++) {
					sum += (A[i][k] * B[k][j]) % 1000;
				}
				r[i][j] = sum % 1000;
			}
		}
		return r;
	}

}