https://www.acmicpc.net/problem/10830
10830번: 행렬 제곱
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
이문제는 행렬의 지수를 절반으로 자르면서 분할계산을 하는 행렬 제곱문제이다.
분할 계산(partition) 문제를 풀기위해서는 짝수일 경우, 홀수일 경우 어떻게 숫자를 탐색해야 하는지 생각해 봐야한다.
먼저 짝수일 경우 계산 과정이다.
위에서 설명했다시피 분할 계산을 해주면 되는데 짝수일 경우는 2로 나누었을 때 나머지가 생기지 않으므로 그냥 나누어서 곱해주면 된다.
다음은 홀수인 경우이다. 홀수의 경우 2로 나누었을 때 딱 나누어 떨어지지 않기 때문에 m11일 경우 m5, m5, m1로 나눈 뒤, 분할 계산을 해주면 된다.
입출력 2번을 보자.
그럼이제 코드를 짜보자.
먼저 BufferedReader와 BuferedWriter를 활용하여 코드를 구현해 보려한다.
package 연습;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class practice {
public static int N;
public static long B;
public static int[][] map;
public static void main(String[] agrs) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
B = Long.parseLong(input[1]);
map = new int[N][N];
for(int i=0; i < N; i++){
input = br.readLine().split(" ");
for(int j=0; j < N; j++){
map[i][j] = Integer.parseInt(input[j]) % 1000;
}
}
int[][] result = partition(B);
for(int i=0; i < N; i++){
for(int j=0; j < N; j++){
bw.write(result[i][j] + " ");
}
bw.write("\n");
}
bw.flush();
}
public static int[][] partition(long count){
if(count == 1){
return map;
}
int[][] result = partition(count / 2);
if(count % 2 == 0){
return multiply(result, result);
}
else{
int[][] result2 = multiply(result, map);
return multiply(result, result2);
}
}
public static int[][] multiply(int[][] A, int[][] B){
int[][] temp = 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++){
temp[i][j] += (A[i][k] * B[k][j]) % 1000;
}
temp[i][j] %= 1000;
}
}
return temp;
}
}
먼저 클래스를 정의해준다.
그리고 public static으로 전역변수 N, B, map을 각각 선언해주었다.
N = 배열의 크기
B = 거듭제곱의 횟수
여기서 B를 int가 아닌 long으로 선언해 주었는데, 문제를 자세히 읽어보면 행렬의 크기가 ( 1 ≤ B ≤ 100,000,000,000)이라고 했으므로
B를 int로 선언하여 코드를 짜게된다면 런타임 에러가 생길 것이다. 그러므로 int형보다 범위가 넓은 long으로 선언하였다.
main메소드를 살펴보자.
이건 예외가 발생했을 때 넘어갈 수 있도록 선언을 해준 것이다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
B = Long.parseLong(input[1]);
map = new int[N][N];
다음은 BufferedReader, BufferedWriter로 각각 읽기 쓰기 입력란을 만들고, input배열을 선언 후 공백을 띄운 채 읽어들이도록 한다.
N, B가 input의 0번째, 1번째로 읽어들이게 만든 후 map배열을 초기화해준다.
다음은 읽어들인 2차원배열 map[N][N]을 공백으로 나눈 뒤, 문제의 조건에 수가 커지기 때문에 1000으로 나누라 했으므로 입력값에서 1000을 나누어 주었다.
B번 거듭제곱한 결과를 계산한 뒤 result[][]배열에 저장을 해준다.
그리고 반복문을 사용하여 result[i][j] +" "로 출력을 해준다.
행렬의 거듭제곱을 구하는 재귀함수 partition이다.
위에서 말했다시피 분할하여 나누는 과정을 계산하는 걸 여기서 구현하였다.
count == 1인 경우에는, 현재 행렬을 그대로 반환해준다.
그리고 result[][] 에 count/2를 재귀해서 계산해준다.
count % 2 == 0 즉, 짝수인 경우에는 result * result 한 결과를 갱신해준다.
홀수인 경우에는 result * map을 한뒤 그것을 다시 result * result2를 해준다.
마지막으로 행렬의 곱셈을 처리하는 multiply 함수이다.
temp[N][N]배열을 생성하고 i,j,k 반복문으로 반복해준다.
A와 B의 해당 위치 요소를 곱한 뒤 1000을 나눈다.
결과를 1000으로 나눈뒤 갱신해준다.
이번엔 bufferedReader를 사용하지 않고 구현해보자.
package 분할정복;
import java.util.Scanner;
public class 행렬제곱 {
public static int N;
public static int[][] map;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
long B = sc.nextLong(); // int로 받으면 런타임에러나니 주의
map = new int[N][N];
for(int i=0; i < N; i++){
for(int j=0; j < N; j++){
map[i][j] = sc.nextInt() % 1000;
}
}
int[][] result = partition(map, 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);
}
public static int[][] partition(int[][] A, long B){
if(B == 1L){
return A;
}
int[][] result = partition(A, B / 2);
result = multiply(result, result);
if(B % 2 == 1L){
result = multiply(result, map);
}
return result;
}
public static int[][] multiply(int[][] A, int[][] B){
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] += A[i][k] * B[k][j];
result[i][j] %= 1000;
}
}
}
return result;
}
}
