[10830] 행렬 제곱

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

10830번: 행렬 제곱

수학 + 분할정복 문제다.

 

풀이

행렬의 제곱연산을 수행하는 함수를 생성. B번의 곱셈을 수행하면 간단하겠지만, B의 최댓값이 크기 때문에 거듭제곱의 원리를 응용하여 연산 횟수를 줄여야 한다.

 

마지막에 출력해 줄 result 배열을 단위행렬로 초기화한 뒤, B가 0이 될 때까지 반복문을 순환한다. 매 반복문마다 A행렬은 거듭제곱연산이 이루어지고, B가 홀수일 경우에는 result배열에 A행렬을 곱해주는 연산을 수행하면 올바른 결과를 출력할 수 있다.

 

A의 7 제곱 행렬을 구한다고 가정했을 경우 아래와 같은 형태로 연산이 수행된다.

B	Result	Matrix
7	A¹	A² = (A¹ * A¹)
3	A¹ * A²	A⁴ = (A² * A²)
1	A¹ * A² * A⁴	A⁸ = (A⁴ * A⁴)
0	결과 출력

 

정답 코드

	import Foundation
	let line = readLine()!.split(separator: " ").map{Int($0)!}
	let N = line[0]
	var B = line[1]
	var matrix = [[Int]]()
	var result = Array(repeating: Array(repeating: 0, count: N), count: N)
	for i in 0..<N{
	result[i][i] = 1
	matrix.append(readLine()!.split(separator: " ").map{Int($0)!})
	}
	func multiple(m:[[Int]], with n:[[Int]]) -> [[Int]]{
	var temp = Array(repeating: Array(repeating: 0, count: N), count: N)
	for i in 0..<N{
	for k in 0..<N{
	for mk in 0..<N{
	temp[i][k] += (m[i][mk]*n[mk][k])%1000
	}
	temp[i][k] %= 1000
	}
	}
	return temp
	}
	while B > 0{
	if B%2==1{
	result = multiple(m: result, with: matrix)
	}
	matrix = multiple(m: matrix, with: matrix)
	B /= 2
	}
	var ans = ""
	for i in 0..<N{
	for k in 0..<N{
	ans.append("\(result[i][k]) ")
	}
	ans.append("\n")
	}
	print(ans)

view raw 10830.swift hosted with ❤ by GitHub