[백준] 11659 구간 합 구하기 4(누적합 - prefixSum)[Kotlin - 코틀린]

백준 11659번 문제입니다. (solved.ac) 기준 실버 3 문제입니다.

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

11659번: 구간 합 구하기 4

 

17390번 이건 꼭 풀어야 해!(누적합 - prefix sum)[Kotlin - 코틀린]

[백준] 17390번 이건 꼭 풀어야 해!(누적합 - prefix sum)[Kotlin - 코틀린]

위의 문제와 굉장히 유사한 문제입니다.

문제

문제 접근

수열이 주어지고 범위가 주어집니다. 수열에서 범위 사이값들의 합을 출력하는 문제입니다.

아주 간단하게 접근하면 수열을 완전탐색하여 범위에 포함하는 값들만 출력해주면 되겠지만 그렇게 접근하면 시간초과가 발생하게 됩니다.

따라서 누적합을 구하는 방법을 이용하여 문제를 해결하였습니다.

 

ex)

누적합을 담을 변수(IntArray) = sumOfSequence가 있습니다.

sumOfSequence[1]에는 수열의 첫 번째값이 저장,

sumOfSequence[2]에는 수열의 첫 번째값 + 두 번째값이 저장= sumOfSequence[1] + 수열의 두 번째값 ,

sumOfSequence[2]에는 수열의 첫 번째값 + 두 번째값 + 세번째 값이 저장 = sumOfSequence[2] + 수열의 세 번째값

이와 같은 방식으로 저장됩니다.

 

sumOfSequence[5] - sumOfSequence[3] => 수열 1 ~ 5번째 값의 합 - 수열 1 ~ 3번째 값의 합 = 수열 4 ~ 5 번째값의 합

임을 이용하여 문제를 해결하였습니다.

정답 코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    val sequence = mutableListOf<Int>()

    br.readLine().split(" ").map { it.toInt() }.forEach {
        sequence.add(it)
    }

    val sumOfSequence = IntArray(sequence.size + 1, { 0 })

    sequence.forEachIndexed { index, curNum ->
        sumOfSequence[index + 1] = sumOfSequence[index] + curNum
    }
    
    repeat(m) {
        val (start, end) = br.readLine().split(" ").map { it.toInt() }
        val answer = sumOfSequence[end] - sumOfSequence[start - 1]
        bw.write("$answer")
    }
    
    bw.flush()
    bw.close()

}