[백준]행렬제곱/10830 풀이 JAVA

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

 

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 

 

풀이(JAVA)

	import java.io.*;
	import java.util.*;
	public class Main {
	final static int MOD = 1000;
	static int N;
	static int[][] A;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// N, B 입력
	StringTokenizer st = new StringTokenizer(br.readLine());
	N = Integer.parseInt(st.nextToken());
	long B = Long.parseLong(st.nextToken());
	// 배열 A 생성
	A = new int[N][N];
	// 배열 A 채우기
	// B=1일 때, pow에서 A 그대로 반환되기 때문에 미리 1000 나눠주기
	for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	for (int j = 0; j < N; j++)
	A[i][j] = Integer.parseInt(st.nextToken()) % MOD;
	}
	int[][] result = pow(A, B);
	// 출력
	StringBuilder sb = new StringBuilder();
	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 int[][] pow(int[][] base, long exponent) {
	// 지수가 1이면 그냥 그대로...
	if (exponent == 1L) return base;
	// 지수의 절반 구하기
	int[][] half = pow(base, exponent / 2);
	// 행렬 제곱하기
	half = mul(half, half);
	// 현재 지수가 홀수면 A 한 번 더 곱해주기
	if (exponent % 2 == 1L) half = mul(half, A);
	return half;
	}
	// 행렬 곱하기
	static int[][] mul(int[][] o1, int[][] o2) {
	int[][] result = new int[N][N];
	for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	for (int k = 0; k < N; k++) {
	result[i][j] += o1[i][k] * o2[k][j];
	result[i][j] %= MOD;
	}
	return result;
	}
	}

view raw Main.java hosted with ❤ by GitHub

---

......헷갈려

.................어려워

행렬은 처음 다뤄보는 거 같은데 쉬운 거 같으면서도 헷갈림

낼 더 공부해야 함