백준 10830 java - 행렬 제곱

문제, 입출력, 테스트케이스

해당 문제는 아래의 두 문제를 조합해서 풀 수 있는 문제이다.

백준 1629 곱셈 문제의 경우 https://chaaany.tistory.com/40?category=957446 본인이 작성한 글이 있으니 참고하면 좋을 것 같다.

백준 1629 java - 곱셈(분할정복)

https://www.acmicpc.net/problem/1629

1629번: 곱셈

https://www.acmicpc.net/problem/2740

2740번: 행렬 곱셈

 

<문제 접근/풀이 과정>
1. 거듭제곱수가 100,000,000,000이므로 계속 하나씩 곱해가는 건 불가능 하겠군
2. 행렬 곱셈의 교환/결합법칙이 성립이 되나? 
-> 일반적인 경우에는 성립이 되지 않지만 정사각형행렬의 경우에는 성립한다.
3. 그렇다면 이전에 곱셈에서 푼대로 거듭제곱 구하듯이 구하면 되겠구나!
4. 근데 행렬의 경우 배열로 표기해야하는데 매번 배열 copyOf하기 귀찮으니까 메서드로 만들어야겠다!

<행렬의 곱을 메서드로 표기한 버전>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
		static int answer[][];
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		StringBuilder sb = new StringBuilder();
		
		stz = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		long B = Long.parseLong(stz.nextToken());
		
		int arr[][] = new int[N][N];
		answer = new int[N][N];
		
		for (int i = 0; i < arr.length; i++) {
			stz = new StringTokenizer(br.readLine());
			for (int j = 0; j < arr.length; j++) {
				arr[i][j] = Integer.parseInt(stz.nextToken());
			}
		}
		for (int i = 0; i < arr.length; i++) {
			answer[i][i] = 1;
		}
		
		power(arr, B, 1000);
		
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < arr.length; j++) {
				sb.append(answer[i][j]%1000).append(" ");
			}
			sb.setLength(sb.length()-1);
			sb.append("\n");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb);
		
		

	}
	private static void power(int[][] arr, long y, int p) {
		int x[][] = new int[arr.length][arr.length];
		
		for (int j = 0; j < x.length; j++) {
			x[j] = Arrays.copyOf(arr[j], arr[j].length);
		}
		
		while(y > 0) {
			if((y & 1) == 1) {
				// 홀수면 바로 이전 행렬 곱해버리기
				answer = matrixBymatix(answer, x);
			}
			
			x = matrixBymatix(x, x);
			y >>= 1;
		}
	}
	
	private static int[][] matrixBymatix(int[][] a, int[][] b){
		int ret[][] = new int[a.length][a.length];
		
		for (int i = 0; i < ret.length; i++) {
			for (int j = 0; j < ret.length; j++) {
				for (int k = 0; k < ret.length; k++) {
					ret[i][k] += (a[i][j]%1000*b[j][k]%1000)%1000;
				}
			}
		}
		
		return ret;
	}
	
}

<행렬의 곱을 메서드로 표기하지 않은 버전 - 코드가 길다..>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
		static int answer[][];
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		StringBuilder sb = new StringBuilder();
		
		stz = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		long B = Long.parseLong(stz.nextToken());
		
		int arr[][] = new int[N][N];
		answer = new int[N][N];
		
		for (int i = 0; i < arr.length; i++) {
			stz = new StringTokenizer(br.readLine());
			for (int j = 0; j < arr.length; j++) {
				arr[i][j] = Integer.parseInt(stz.nextToken());
			}
		}
		for (int i = 0; i < arr.length; i++) {
			answer[i][i] = 1;
		}
		
		power(arr, B, 1000);
		
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < arr.length; j++) {
				sb.append(answer[i][j]%1000).append(" ");
			}
			sb.setLength(sb.length()-1);
			sb.append("\n");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb);
		
		

	}
	private static void power(int[][] arr, long y, int p) {
		int x[][] = new int[arr.length][arr.length];
		
		for (int j = 0; j < x.length; j++) {
			x[j] = Arrays.copyOf(arr[j], arr[j].length);
		}
		
		while(y > 0) {
			if((y & 1) == 1) {
				// 홀수면 바로 이전 행렬 곱해버리기
				int temp1[][] = new int[arr.length][arr.length];
				
				for (int j = 0; j < x.length; j++) {
					temp1[j] = Arrays.copyOf(answer[j], answer[j].length);
				}
				
				int temp2[][] = new int[arr.length][arr.length];
				
				for (int j = 0; j < x.length; j++) {
					temp2[j] = Arrays.copyOf(x[j], x[j].length);
				}
				
				answer = new int[arr.length][arr.length];
				
				for (int i = 0; i < arr.length; i++) {
					for (int j = 0; j < arr.length; j++) {
						for (int k = 0; k < arr.length; k++) {
							answer[i][k] += (temp1[i][j]%1000*temp2[j][k]%1000)%1000;
						}
					}
				}
			}
			
			int temp[][] = new int[arr.length][arr.length];
			
			for (int j = 0; j < x.length; j++) {
				temp[j] = Arrays.copyOf(x[j], x[j].length);
			}
			
			x = new int[arr.length][arr.length];
			
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr.length; j++) {
					for (int k = 0; k < arr.length; k++) {
						x[i][k] += (temp[i][j]%1000*temp[j][k]%1000)%1000;
					}
				}
			}
			y >>= 1;
		}
	}
	
}

 

코드 작성할 때 계속 이미 존재하는 행렬에 더하는 식으로 해서 답 안 나와서 1시간 동안 삽질했는데 결국 깨달아서 겨우겨우 풀었다... 흑흑 다음부터는 주석 잘 달면서 코딩해야겠다!