728x90
https://www.acmicpc.net/problem/10830
이 문제를 풀기전에 아래의 두 문제를 먼저 풀으시는 것을 추천드립니다!
1. 행렬 곱셈
https://www.acmicpc.net/problem/2740
-> 풀이
https://iheeeee6-6.tistory.com/51
2. 곱셈
https://www.acmicpc.net/problem/1629
-> 풀이
https://iheeeee6-6.tistory.com/52
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
우선 이 문제는 분할 정복으로 해결할 수 있습니다.
행렬을 곱하면서 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;
}
}
'Java' 카테고리의 다른 글
[백준 1629] 곱셈 (JAVA) (0) | 2023.03.12 |
---|---|
[백준 2740] 행렬 곱셈 (JAVA) (0) | 2023.03.12 |
[백준 1474] 밑 줄 (JAVA) (0) | 2023.03.09 |
[백준 11659] 구간 합 구하기 4 (JAVA) (0) | 2023.03.09 |
[백준 1389] 케빈 베이컨의 6단계 법칙 (JAVA) (1) | 2023.03.06 |