[Algorithm] 백준 - 11660번 구간 합 구하기 5 (Swift)

문제 소개

풀이 과정

아주아주 단순하게 문제에 접근하면 아래와 같이 할 수 있을 것이다. 단순히 table을 만든 후 아래처럼 입력값에 따라서 성실하게(?) 답변을 구현한다. 물론 이렇게 풀게된다면 M 100,000이고, N 1,024일때 최악의 경우 1,024 x 1,024 x 100,000번 연산을 해야하기 때문에 시간초과다. ☠️

import Foundation

let nm = readLine()!.components(separatedBy: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
var table = [[Int]]()

for _ in 0..<n {
    table.append(readLine()!.components(separatedBy: " ").map { Int($0)! })
}

for _ in 0..<m {
    let input = readLine()!.components(separatedBy: " ").map { Int($0)! }
    let (x1, y1, x2, y2) = (input[0]-1, input[1]-1, input[2]-1, input[3]-1)
    
    var result = 0
    
    for i in x1...x2 {
        for j in y1...y2 {
            result += table[i][j]
        }
    }
    
    print(result)
}

어떻게 이문제를 해결 할 수 있을까? 아래와 같은 개념을 사용하면 된다. dp로 [1][1]부터 [i][j]의 누적합을 구하게 된다면 아래와 같은 연산으로 선택한 영역의 합을 구할 수 있다.

.....       ooooo     oo...     ooooo     oo...
..ooo   =   ooooo  -  oo...  -  .....  +  .....
..ooo       ooooo     oo...     .....     .....

또한 입력값이 10만이 넘기 때문에 FileIO라이브러리를 활용했다...

import Foundation

final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)]
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        
        return buffer[index]
    }
    
    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true
        
        while now == 10
                || now == 32 { now = read() }
        if now == 45 { isPositive.toggle(); now = read() }
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }
        
        return sum * (isPositive ? 1:-1)
    }
    
    @inline(__always) func readString() -> String {
        var now = read()
        
        while now == 10 || now == 32 { now = read() }
        
        let beginIndex = index-1
        
        while now != 10,
              now != 32,
              now != 0 { now = read() }
        
        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }
    
    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()
        
        while now == 10 || now == 32 { now = read() }
        
        let beginIndex = index-1
        
        while now != 10,
              now != 32,
              now != 0 { now = read() }
        
        return Array(buffer[beginIndex..<(index-1)])
    }
}
let fIO = FileIO()

let n = fIO.readInt()
let m = fIO.readInt()
var dp = Array(repeating: Array(repeating: 0, count: n+2), count: n+2)

// 값 입력
for i in 1...n {
    for j in 1...n {
        let input = fIO.readInt()
        dp[i][j] = input
    }
}

// 누적합 계산
for i in 1...n {
    for j in 1...n {
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    }
}

// 계산된 dp활용
for _ in 0..<m {
    let x1 = fIO.readInt()
    let y1 = fIO.readInt()
    let x2 = fIO.readInt()
    let y2 = fIO.readInt()
    print(dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1])
}