BOJ-10830 행렬 제곱 Swift

문제

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

입력

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

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

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

내가 푼 풀이

접근방법: 분할정복

첫번째로 행렬의 곱셈을 먼저 구현한다. (for 3중반복문)

거듭제곱을 그대로 곱하면 1000억번 연산해야하므로 시간초과가 무조건 난다.

여기서 거듭제곱을 지수법칙을 적용해 분할정복 형식으로 곱한다.

 

$ A^{B} = A^{\frac{B}{2}} \times A^{\frac{B}{2}} $ 이 성립하므로 지수가 주어지면 1이 될때까지 반으로 분할한다.

지수가 홀수:

 $A^{B} = A^{\frac{B}{2}} \times A^{\frac{B}{2}} \times A $

지수가 짝수:

 $A^{B} = A^{\frac{B}{2}} \times A^{\frac{B}{2}}$

 

1까지 분할이 됬다면 두 행렬을 곱한다(정복)

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
var input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], B = input[1]
var arr = [[Int]]()
for i in 0..<N {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

// 분할 정복
func divide(_ N: [[Int]],_ B: Int) -> [[Int]]{
    // 지수가 1이 될때 까지 분할
    if B == 1 {
        return N
    }
    // 지수를 반으로 분할
    let m = divide(N, B/2)
    // 지수가 짝수인경우 나머지가 없으므로 나눈 두 행렬을 곱
    if B % 2 == 0 {
        return multi(m, m)
    } else {
        // 지수가 홀수라면 나머지1이 존재하므로 나눈 두 행렬과 지수가 1인 행렬 곱
        return multi(multi(m, m), N)
    }
}
//행렬 곱
func multi(_ x: [[Int]],_ y: [[Int]]) -> [[Int]] {
    var result = 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] += ((x[i][k] * y[k][j]))
            }
            result[i][j] %= 1000
        }
    }
    return result
}

// 지수가 1이고, 행렬의 원소가 1000 이상이라면 출력은 해당원소를 1000으로 나눠야 하므로 한번 나눠준다.
var result = divide(arr, B)
for i in 0..<result.count {
    for j in 0..<result[i].count {
        result[i][j] %= 1000
    }
}

// 출력
for i in 0..<result.count {
    print(result[i].map{String($0)}.joined(separator: " "))
}