[BOJ/백준][Silver3] 11659 : 구간 합 구하기4 (Kotlin)

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

11659번: 구간 합 구하기 4

 

 

 

[난이도] Silver3
[유형] 누적합

[풀이]
구간합 배열 sum을 만들어놓고 sum[j]-sum[i] 형태로 모든 쿼리에 O(1)로 출력이 가능합니다.

 

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var (N,M) = readLine().split(' ').map{it.toInt()}
    val arr = readLine().split(' ').map{it.toInt()}
    val sum = Array<Int>(N){0}
    sum[0]=arr[0]
    for(i in 1 until N) sum[i] = sum[i-1]+arr[i]
    while(M-->0){
        val ip = readLine().split(' ')
        val i = ip[0].toInt()
        val j = ip[1].toInt()
        println(sum[j-1]-(if(i==1) 0 else sum[i-2]))
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/11659.cpp