[백준 알고리즘 #11659] 구간 합 구하기4

개념

a부터 b까지의 합을 구한다 했을 때, (b까지의 누적 합) - (a-1까지의 누적 합)을 적용하여 누적된 수의 합을 구하는 개념이다.

예를 들자면 아래와 같다. [5,4,3,2,1]까지의 합이 있다. 그리고 누적합 배열을 만든다. [5, 9, 12, 14, 15]와 같이 말이다. 이때 2번째부터 4번째까지의 누적 합을 구한다 했을 때, 14 - 5를 적용하여 9를 계산한다.

누적합 사용 이점

위와 같은 절차가 1번만 있다면 큰 문제가 없다. 다만, 숫자의 갯수가 극적으로 많아지고, 구간 합 계산 횟수가 많아질 때 시간복잡도는 극적으로 올라간다. 따라서 이를 줄이기 위해 구간 합에 해당하는 배열을 미리 구하는 것을 끝으로 반복문 실행을 안하게 할 수 있다. 이로써 시간 복잡도가 줄어든다.

11659번 알고리즘 풀이

[깃허브 풀이과정 보러 가기]

import java.lang.StringBuilder

fun main() {
    val sumCount = readln().split(' ').run { get(1).toInt() }
    val numbers = readln().split(' ').map { it.toInt() }
    val accumeratedNumbers = mutableListOf<Int>()
    val sb = StringBuilder()

    for (index in numbers.indices) {
        if (index == 0) accumeratedNumbers.add(numbers[0])
        else {
            accumeratedNumbers.add(accumeratedNumbers[index - 1] + numbers[index])
        }
    }

    for (index in 0 until sumCount) {
        val range = readln().split(' ').run { listOf(get(0).toInt(), get(1).toInt()) }
        val start = range[0]
        val end = range[1]

        val result = if (start == 1) accumeratedNumbers[end - 1]
        else accumeratedNumbers[end - 1] - accumeratedNumbers[start - 2]

        sb.append("$result\n")
    }
    print(sb)
}