[Gold IV] 행렬 제곱 - 10830
성능 요약
메모리: 12892 KB, 시간: 112 ms
분류
분할 정복(divide_and_conquer), 분할 정복을 이용한 거듭제곱(exponentiation_by_squaring), 선형대수학(linear_algebra), 수학(math)
문제 설명
크기가 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제곱한 결과를 출력한다.
행렬 제곱은 정사각형인 행렬에서만 가능하다.
예를 들어
1 2
3 4
로 구성된 행렬을 제곱한다면 다음과 같을 것이다
행렬 곱을 한 배열의 index를 (r, c)라고 하고, 전체 행렬의 크기를 n이라고 하면
result[r][c] = map[0][c]*map[r][0] + map[1][c]*map[r][1] ... + map[n-1][c]*map[r][n-1] 이 될 것이다.
static long[][] multiMatrix(long[][] a, long[][] b) {
long[][] tmp = new long[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
for (int d = 0; d < N; d++)
tmp[i][j] = (tmp[i][j] + a[d][j] * b[i][d]) % 1000;
}
return tmp;
}
제곱은 이렇게 구할 수 있는데, 거듭제곱은 어떻게 구할 수 있을까?
분할 정복을 이용하면 거듭제곱의 지수가 큰 경우에도 빠르게 계산할 수 있다.
예를 들어 행렬 A를 25제곱 하는 경우
$$ A^{25} = (A^{12}) ^2 * A $$
가 될 것이다.
이를 반복하면 간단하게 A의 거듭제곱을 구할 수 있다.
static long[][] mul(long B) {
if (B == 1)
return map;
long[][] tmp = mul(B / 2);
if (B % 2 == 0)
return multiMatrix(tmp, tmp);
else
return multiMatrix(multiMatrix(tmp, tmp), map);
}
전체 코드
package Gold.g4;
import java.util.Scanner;
public class BOJ_10830_행렬제곱 {
static long[][] map;
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
long B = sc.nextLong(); // 범위 long
map = new long[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
map[i][j] = sc.nextLong();
long[][] result = mul(B);
for (long[] arr : result) {
for (int i = 0; i < N; i++)
System.out.print(arr[i] % 1000 + " "); // 처음부터 arr[i]가 1000일 경우 1000이 아니라 0 출력하기
System.out.println();
}
}
static long[][] mul(long B) {
if (B == 1)
return map;
long[][] tmp = mul(B / 2);
if (B % 2 == 0)
return multiMatrix(tmp, tmp);
else
return multiMatrix(multiMatrix(tmp, tmp), map);
}
static long[][] multiMatrix(long[][] a, long[][] b) {
long[][] tmp = new long[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
for (int d = 0; d < N; d++)
tmp[i][j] = (tmp[i][j] + a[d][j] * b[i][d]) % 1000;
}
return tmp;
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 2630 - 색종이 만들기 (자바/Java) (0) | 2022.09.20 |
---|---|
[백준] 17070 - 파이프 옮기기 1 (자바/Java) (0) | 2022.09.20 |
[백준] 1074 - Z (자바/Java) (0) | 2022.09.20 |
[백준] 10972 - 다음 순열 (자바/Java) (0) | 2022.09.20 |
[백준] 2448 별 찍기 - 11 (자바/Java) 재귀, 분할정복 (0) | 2022.09.19 |