[백준/BOJ] 11659번: 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

문제

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

해설

문제를 처음 봤을 때 M번 반복을 할 반복문 안에 i부터 j까지의 합을 구할 반복문을 하나 더 민들어 이중 반복문을 통해 풀었다.

for(i in 0 until M) {
    var sum = 0
    for(a in i .. j) {
        sum += arr[a]
    }
}

하지만 이렇게 풀었더니 시간 초과가 났다.

 

해결법을 찾아보니 prefix sum 알고리즘을 알게 되었다.

prefix sum 알고리즘이란 부분합을 미리 구해 놓고 start - 1의 값을 빼주면 된다.

이를 이용하면 이중 for문을 쓸 필요없이 단일 for문으로 문제를 해결할 수 있다.

 

prefix sum 알고리즘을 사용한 코드를 보면 좀 더 이해하기 쉬울 것이다.

소스 코드

import java.util.*

fun main() {
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()

    val arr = IntArray(100001) { 0 }
    st = StringTokenizer(readLine())
    for(i in 1 .. n) arr[i] = st.nextToken().toInt()

    val sum = IntArray(100001)
    for(i in 0 .. n) {
        if(i == 0) sum[i] = arr[i]
        else sum[i] = sum[i-1] + arr[i]
    }

    for(i in 0 until m) {
        st = StringTokenizer(readLine())
        val start = st.nextToken().toInt()
        val end = st.nextToken().toInt()
        println(sum[end] - sum[start-1])
    }
}