[Swift 백준] 11660 구간 합 구하기 5

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

 

풀이 아이디어

2차원 배열에서의 누적합 문제입니다.

 

공식은 다음과 같습니다

 

S[x2][y2]−S[x1−1][y2]−S[x2][y1−1]+S[x1−1][y1−1]

 

• S[x2][y2] : (1,1) ~ (x2,y2)까지의 누적합 (구하고 싶은 영역을 포함한 더 넓은 부분)
• - S[x1-1][y2] : 위쪽(x1-1 행)까지의 합을 빼줌
• - S[x2][y1-1] : 왼쪽(y1-1 열)까지의 합을 빼줌
• + S[x1-1][y1-1] : 너무 많이 빼진 왼쪽 위 영역을 다시 더해줌

 

풀이

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])

var graph = [[Int]]()
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    graph.append(input)
}

var prefixGraph = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)

for i in 1...n {
    for j in 1...n {
        prefixGraph[i][j] = graph[i - 1][j - 1]
                            + prefixGraph[i - 1][j]
                            + prefixGraph[i][j - 1]
                            - prefixGraph[i - 1][j - 1]
    }
}

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let (x1, y1, x2, y2) = (input[0], input[1], input[2], input[3])

    let result = prefixGraph[x2][y2]
                - prefixGraph[x1 - 1][y2]
                - prefixGraph[x2][y1 - 1]
                + prefixGraph[x1 - 1][y1 - 1]

    print(result)
}