[백준/코틀린] 11660번: 구간 합 구하기 5

링크

11660번: 구간 합 구하기 5

풀이

테이블의 모든 위치까지의 누적 합을 미리 계산해
2차원 누적 합(prefix sum) 테이블을 만들어두면,
구간 [(y1, x1) ~ (y2, x2)]의 합을 O(1)에 구할 수 있습니다.

2차원 누적 합 테이블

출처: Wikipedia: Summed-area table

생성

누적 합 테이블을 생성할 때,
(i, j)위치의 누적 합 prefixSum[i][j]은 다음과 같이 계산됩니다.

• nums[i][j]: 해당 위치의 값
• prefixSum[i - 1][j]: 위쪽 영역의 누적 합
• prefixSum[i][j - 1]: 왼쪽 영역의 누적 합
• prefixSum[i - 1][j - 1]: 겹치는 부분(왼쪽 위)의 누적 합

\[\begin{aligned} \text{prefixSum}[i][j] &= \text{nums}[i][j] \\ &+ \text{prefixSum}[i-1][j] \\ &+ \text{prefixSum}[i][j-1] \\ &- \text{prefixSum}[i-1][j-1] \end{aligned}\]

계산

예를 들어, 위와 같이 누적 합 테이블을 미리 계산해 두었다면,
구간 [(4, 3) ~ (5, 5)]의 합은 다음처럼 구할 수 있습니다.

• prefixSum[3][2]: 겹치는 영역 = 28
• prefixSum[5][5]: 전체 영역 = 110
• prefixSum[3][5]: 위쪽 제외 = 65
• prefixSum[5][2]: 왼쪽 제외 = 46

\[\begin{aligned} \text{sum}[(4,3),(5,5)] &= \text{prefixSum}[3][2] \\ &+ \text{prefixSum}[5][5] \\ &- \text{prefixSum}[3][5] \\ &- \text{prefixSum}[5][2] \\ &= 27 \end{aligned}\]

코드

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val nums = List(n) { readln().split(" ").map { it.toInt() } }
    val prefixSum = Array(n + 1) { IntArray(n + 1) }

    for (i in 1..n) {
        for (j in 1..n) {
            prefixSum[i][j] = nums[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]
        }
    }

    repeat(m) {
        val (x1, y1, x2, y2) = readln().split(" ").map { it.toInt() }

        println(prefixSum[x2][y2] - prefixSum[x2][y1 - 1] - prefixSum[x1 - 1][y2] + prefixSum[x1 - 1][y1 - 1])
    }
}

연관 문제

• [백준/코틀린] 11659번: 구간 합 구하기 4 - 1차원 누적합