[백준] 10830.행렬 제곱 (Swift, Java)

[백준] 10830.행렬 제곱 (Swift, Java)

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

10830번: 행렬 제곱

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

이해

1. 단순 제곱

문제를 처음 읽었을 때 당연히 처음 떠오르는 해답은 단순 제곱이었습니다. 행렬을 B 번 만큼 곱해주면 되는거 아냐? 라는 생각이 들면서도 역시 문제가 그렇게 단순할 리 없다는 생각과, O(B^2) 만큼의 시간이 걸릴것이라고 예상했기 때문에 해당 방법은 과감하게 버렸습니다.

2. 이진탐색 - O(logN)

가장 힌트가 되었던건 시간복잡도였습니다. 어떤 식으로 문제를 풀어야 할지 몰라 검색 도중, O(logN) 이라는 키워드가 가장 큰 아이디어가 되었습니다.

 

이진탐색은 데이터를 반씩 나누어가며 탐색하는 방법으로 이진트리의 모양을 하고있어 시간복잡도가 O(logN) 이지만, 저는 이진탐색의 역순(?)과 비슷한 방향으로 문제를 풀어나갔습니다.

---

먼저 제곱을 해야하는 횟수를 N 이라고 하고, N 은 11 이 주어졌다고 가정하겠습니다.

그림에서 각 원은 행렬을 뜻합니다.

---

그 다음 행렬을 2개씩 짝지어 곱셈을 진행합니다. 이때 N 이 홀수라면 무조건 하나의 행렬이 남게 되는데, 이는 odd 라는 이름의 변수에 저장해둡니다.

 

행렬을 2개씩 짝지어 곱셈을 진행했기 때문에 남은 연산 수는 1/2 이 됩니다. 그렇기 때문에 N/2 인 5 를 다시 N 에 저장해줍니다.

---

다시 행렬을 두개씩 짝지어 곱해주고 N/=2 를 진행합니다. 5 또한 홀수이기 때문에 하나의 행렬이 남게 되는데 이는 이전에 존재하던 odd 와 곱해준 후 그 결과값을 다시 odd 에 저장해줍니다.

 

odd 를 계속해서 업데이트 시켜주는 이유는 짝지어 계산한 마지막 결과에 곱해주기 위함입니다.

이후 남은 2개의 행렬을 곱해주고 N/=2 를 진행합니다. N이 1이 되었기 때문에 더 이상 짝지어 곱해줄 행렬을 존재하지 않습니다.

---

하지만 아직 곱해주지 않은 나머지 행렬 odd 가 남았기 때문에 이 둘을 곱해주면 정답이 도출되게 됩니다.

위 그림은 이진트리의 모양을 하고있기 때문에 O(logN) 의 시간복잡도를 가지게 됩니다.

---

전체 코드

Swift

	import Foundation
	// 행렬의 곱을 반환해주는 메소드
	func multiple(_ matrix_01: [[Int]], _ matrix_02: [[Int]], _ n: Int) -> [[Int]] {
	var result: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n)
	for i in 0 ..< n {
	for j in 0 ..< n {
	for k in 0 ..< n {
	result[i][j] += matrix_01[i][k] * matrix_02[k][j]
	result[i][j] %= 1000
	}
	}
	}
	return result
	}
	// 마지막 결과 출력 메소드
	func printMatrix(_ matrix: [[Int]], _ n: Int) {
	for i in 0 ..< n {
	var line: String = ""
	for j in 0 ..< n {
	line += "\(matrix[i][j] % 1000) "
	}
	print(line)
	}
	}
	var input: [Int] = readLine()!.split(separator: " ").map { Int($0)! }
	var n: Int = input[0]
	var square: Int = input[1]
	var matrix: [[Int]] = []
	var odd: [[Int]] = []
	for _ in 0 ..< n {
	matrix.append(readLine()!.split(separator: " ").map { Int(String($0))! })
	}
	// 더 이상 짝지어 곱해줄 행렬이 남지 않을때까지
	while square > 1 {
	// 만약 홀수라면
	if square % 2 == 1 {
	// odd 가 없을때는 그냥 odd 에 저장
	if odd.isEmpty {
	odd = matrix
	}
	// odd 가 이미 존재한다면 곱해준 다음 저장
	else {
	odd = multiple(matrix, odd, n)
	}
	}
	// 계속 제곱을 해주고
	matrix = multiple(matrix, matrix, n)
	// 제곱수는 /2
	square /= 2
	}
	if odd.isEmpty {
	printMatrix(matrix, n)
	} else {
	matrix = multiple(matrix, odd, n)
	printMatrix(matrix, n)
	}

view raw BOJ_10830.swift hosted with ❤ by GitHub

Java

	import java.io.*;
	import java.util.StringTokenizer;
	public class Main {
	public static void main(String[] args) throws IOException, NumberFormatException {
	BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
	StringTokenizer tokenizer = new StringTokenizer(input.readLine());
	int n = Integer.parseInt(tokenizer.nextToken());
	long square = Long.parseLong(tokenizer.nextToken());
	int[][] matrix = new int[n][n];
	int[][] odd = new int[n][n];
	boolean isOddEmpty = true;
	for (int i = 0; i < n; i++) {
	tokenizer = new StringTokenizer(input.readLine());
	for (int j = 0; j < n; j++) {
	matrix[i][j] = Integer.parseInt(tokenizer.nextToken());
	}
	}
	// 더 이상 짝지어 곱해줄 행렬이 남지 않을때까지
	while (square > 1) {
	// 만약 홀수라면
	if (square % 2 == 1) {
	// odd 가 없을때는 그냥 저장
	if (isOddEmpty) {
	odd = matrix;
	isOddEmpty = false;
	}
	// odd 가 이미 존재한다면 곱해준 다음 저장
	else {
	odd = multiple(matrix, odd, n);
	}
	}
	// 계속 제곱해주고
	matrix = multiple(matrix, matrix, n);
	// 제곱수는 /2
	square /= 2;
	}
	if (isOddEmpty) {
	printMatrix(matrix, n, output);
	} else {
	matrix = multiple(matrix, odd, n);
	printMatrix(matrix, n, output);
	}
	output.flush();
	output.close();
	input.close();
	}
	// 행렬 곱셈 메소드
	public static int[][] multiple(int[][] matrix_01, int[][] matrix_02, int n) {
	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] += matrix_01[i][k] * matrix_02[k][j];
	result[i][j] %= 10000;
	}
	}
	}
	return result;
	}
	// 마지막 결과값 출력 메소드
	public static void printMatrix(int[][] matrix, int n, BufferedWriter output) throws IOException {
	for (int i = 0; i < n; i++) {
	String line = "";
	for (int j = 0; j < n; j++) {
	output.write(matrix[i][j] % 1000 + " ");
	}
	output.write("\n");
	}
	}
	}

view raw BOJ_10830.java hosted with ❤ by GitHub