문제
https://www.acmicpc.net/problem/10830
10830번: 행렬 제곱
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
풀이
밑이 같은 두 거듭제곱의 곱은 밑은 그대로 쓰고 지수만 더해준다는 지수법칙을 활용한다.
예를 들어 2의 10제곱은 2^10 = 2^5 * 2^5 로 분할 할 수 있다.
그러면 2를 10번 곱하는게 아닌 2를 5번 곱한 값을 가져와서 제곱을 하면 된다.
2^5 또한 아래와 같이 분할 할 수 있다.
2^5 = 2^2 * 2^2 * 2
이렇게 지수의 거듭제곱을 절반 씩 분할 하면서 제곱 계산의 수를 현저히 줄일 수 있다.
소스코드
package divideconquer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ10830 {
public static int N;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.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(br.readLine());
for(int j = 0; j < N; j++){
arr[i][j] = Long.parseLong(st.nextToken());
}
}
long[][] answer = pow(arr, B);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
System.out.print(answer[i][j]%1000 + " ");
}
System.out.println();
}
}
public static long[][] pow(long[][] base, long B){
if(B == 1) return base;
long[][] temp = null;
if(B % 2 == 0) {
temp = pow(base, B/2);
return multiply(temp, temp);
} else {
temp = pow(base,(B-1)/2);
return multiply(base, multiply(temp, temp));
}
}
public static long[][] multiply(long[][] arr1, long[][] arr2){
long[][] answer = new long[N][N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
long ans = 0;
for(int k = 0; k < N; k++){
ans += arr1[i][k]*arr2[k][j]%1000;
}
answer[i][j] = ans%1000;
}
}
return answer;
}
}
'💡Problem Solving > BOJ' 카테고리의 다른 글
[BOJ 1238] 파티 (Java) (0) | 2021.11.26 |
---|---|
[BOJ 4485] 녹색 옷 입은 애가 젤다지? (Java) (0) | 2021.11.26 |
[BOJ 11444] 피보나치 수 6 (Java) (0) | 2021.11.24 |
[BOJ 2981] 검문 (Java) (0) | 2021.11.24 |
[BOJ 1707] 이분 그래프 (Java) (0) | 2021.11.23 |