반응형
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())
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
백준 7511번 소셜 네트워킹 어플리케이션 - 스위프트(Swift) 시간초과 해결 (0) | 2022.01.24 |
---|---|
백준 1043번 거짓말 - 스위프트(Swift) 풀이 (0) | 2022.01.24 |
백준 9465번 스티커 - 스위프트(Swift) 풀이 (0) | 2022.01.22 |
백준 9019번 DSLR - 스위프트(Swift) 시간초과 해결 (0) | 2022.01.21 |
백준 6064번 카잉 달력 - 스위프트(Swift) 풀이 + 그림 설명 (0) | 2022.01.21 |
댓글