백준 10830번 행렬 제곱 - 스위프트(Swift) 풀이

1. 분할 정복으로 해결한다.
2. B % 2 = 0인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * multiplyMatrix(B/2)
3. B % 2 = 1인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * multiplyMatrix(B/2) * A
4. 메모이제이션을 통해 연산 횟수를 줄인다.
5. 초기 행렬에 1000이 있는 경우를 조심한다.

---

1. 분할 정복으로 해결한다.

 진짜로 B제곱을 하면 B가 10^12로 엄청 크기 때문에 당연히 시간 초과가 난다. 대신 유명한 알고리즘인 분할 정복을 이용한 거듭제곱을 사용한다.

 

2. B % 2 = 0인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * multiplyMatrix(B/2)

  B가 짝수인 경우, B/2제곱 결과를 또다시 제곱하면 된다.

 

3. B % 2 = 1인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * multiplyMatrix(B/2) * A

 B가 홀수인 경우 B/2제곱 * B/2 제곱 * 1 제곱으로 구할 수 있다.

 

 

4. 메모이제이션을 통해 연산 횟수를 줄인다.

 multiplyMatrix(B)를 구했으면 캐시에 기록해둔다. 이후 또 multiplyMatrix(B)를 호출했을 때, 기저 사례까지 내려가서 구할 필요 없도록 캐시에 기록해둔 값을 바로 리턴해준다. 이렇게 메모이제이션을 통해 연산 횟수를 줄일 수 있다. B가 10^12이므로 딕셔너리를 이용해서 메모이제이션을 구현하였다.

 

 

5. 초기 행렬에 1000이 있는 경우를 조심한다.

  입력 값에 약간의 함정이 있는데, 행렬의 각 원소에 1000도 들어올 수 있다는 것이다. 기저 사례를 B = 1로 잡아서 이때는 그냥 행렬을 그대로 리턴해주게 짜면 1000 % 1000 = 0이 아니라 1000을 그대로 출력하게 된다. 이 부분 고려안했다가 WA를 한번 받았다ㅠㅠ

 

---

import Foundation

struct Matrix: CustomStringConvertible {
    let matrix: [[Int]]
    
    var size: Int {
        return matrix.count
    }
    
    subscript(index: Int) -> [Int] {
        return matrix[index]
    }
    
    static func *(lhs: Matrix, rhs: Matrix) -> Matrix {
        var result = Array(repeating: Array(repeating: 0, count: lhs.size), count: lhs.size)
        
        for i in 0..<lhs.size {
            for j in 0..<lhs.size {
                for k in 0..<lhs.size {
                    result[i][j] += (lhs[i][k] * rhs[k][j]) % 1000
                    result[i][j] %= 1000
                }
            }
        }
        
        return Matrix(matrix: result)
    }
    
    var description: String {
        var ret = ""
        
        for i in 0..<size {
            for j in 0..<size {
                ret.write("\(matrix[i][j] % 1000) ")
            }
            ret.write("\n")
        }
        
        return ret
    }
}

var cache = [Int64:Matrix]()

func multiplyMatrix(matrix: Matrix, n: Int64) -> Matrix {
    if n == 1 { return matrix }
    
    if let ret = cache[n] { return ret }
    
    let halfResult = multiplyMatrix(matrix: matrix, n: n / 2)
    
    if n % 2 == 0 {
        cache[n] = halfResult * halfResult
        return cache[n]!
    } else {
        cache[n] = halfResult * halfResult * matrix
        return cache[n]!
    }
}

func solution() -> String {
    let input = readLine()!.split(separator: " ").map{ Int64(String($0))! }
    let N = input[0]
    let B = input[1]
    
    var matrix = [[Int]]()
    
    for _ in 0..<N {
        matrix.append(readLine()!.split(separator: " ").map{ Int(String($0))! })
    }
    
    return multiplyMatrix(matrix: Matrix(matrix: matrix), n: B).description
}

print(solution())