[BOJ/Kotlin] 11659번 구간 합 구하기 4 : 누적합

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

문제 풀이 아이디어

실패 아이디어 
입력값으로 주어지는 각 값을 똑같은 위치에 배열에 저장해서 for문을 돌면서 i 인덱스부터 j 인덱스까지 접근해 값을 더하는 식으로 문제를 풀었다 => 시간초과

성공 아이디어
d[i]에 처음부터 i번째까지 값들을 전부 더해온 누적값을 저장하고, 누적값들을 이용해 구간합을 구하는 방식으로 문제를 풀었다.

생각해야할 케이스가 3개라고 생각했다.
시작이 1인 경우 (1,i) => 그냥 d[i]를 출력하면된다. 처음부터 i번째까지 값을 다 더한 누적값이 저장되어있기 때문이다.

start와 end가 똑같을 경우 (i==j) => d[end] - d[end-1] 을 출력하면된다. d[end-1]에서 입력의 end 번째 값이 더해진 것이 d[end]이기 때문이다.

그 외 경우 => 시작이 1도 아니고, start와 end가 다른 경우이다. 이 때는 d[end] - d[start-1]을 출력하면 된다.

위 식은 입력 예시를 바탕으로 도출할 수 있었다.

5 3
5 4 3 2 1
1 3
2 4
5 5

이렇게 있을 때 d 배열의 값을 출력하면 아래와 같이 나온다.

0 5 9 12 14 15

(1번째 값은 index 1에 들어가도록 만든거라, 0번째 인덱스는 무시해도된다.)

이때 2 4 입력값의 경우에는 4,3,2 가 더해진 = 9가 출력되어야한다. 9가 출력되기 위해서는 4번째 14 - 5 가 되어야하므로 
d[4] - d[1] 이 된다. 모든 경우에도 동일하게 적용된다. 따라서 일반화하면 d[end] - d[start-1] 이다.

코드

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val N = input[0].toInt()
    val M = input[1].toInt()
    var d = Array(N + 1) { 0 }
    var answerList: MutableList<Int> = mutableListOf()

    val num = readLine().split(" ")
    for (i in 1 until N + 1) {
        d[i] = num[i - 1].toInt() + d[i - 1]
    }

    for (i in 0 until M) {
        val str = readLine().split(" ")
        val start = str[0].toInt()
        val end = str[1].toInt()

        if (start == 1) {
            answerList.add(d[end])
        } else if (start == end) {
            answerList.add(d[end] - d[end - 1])
        } else {
            answerList.add(d[end] - d[start - 1])
        }
    }

    answerList.forEach {
        println(it)
    }
}