11441번: 합 구하기 - Kotlin (누적 합)

11441번: 합 구하기

문제

N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

출력

총 M개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다.

 

나의 풀이

 이 문제는 구간의 합을 구하면 되는 문제이다. 1부터 10까지의 합에서 만약 4부터 10까지의 합을 구하려고 한다면, 1부터 10까지의 합에서 1부터 3까지의 합을 빼면 해당 구간의 합을 구할 수 있다. 이를 코드로 구현하면 된다. 주어진 숫자들의 양이 상당히 많기에 DP를 사용해서 해결하면 된다.

 

import kotlin.math.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val num = readLine().split(" ").map { it.toInt() }

    val dp = IntArray(n + 1)

    for (i in 1..n) {
        dp[i] = num[i - 1] + dp[i - 1]
    }

    val m = readLine().toInt()
    repeat(m) {
        val (start, end) = readLine().split(" ").map { it.toInt() }

        println(dp[end] - dp[start - 1])
    }
}