백준 11441 합 구하기 Kotlin (누적 합)

문제 출처 : https://www.acmicpc.net/problem/11441

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개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다.

알고리즘 분류

• 누적 합

풀이

0부터 n까지의 누적 합을 구한 후에,

누적 합을 이용해 구간 합을 구하는 누적 합, 구간 합 기본 문제이다.

누적 합을 구하는 방법은

1, 3, 2, 4 ,5의 숫자 리스트가 있다고 할 때, 우선

arr = {0, 1, 3, 2, 4, 5}로 입력 받는다.

이후 누적 합의 첫 번째 원소는 0으로 넣어두고,

pSum[1] = pSum[1-1] + arr[1]

pSum[2] = pSum[2-1] + arr[2]

.

.

pSum[n] = pSum[n-1] + arr[n] 

이런 방식으로 누적 합 배열을 만들 수 있다.

이후 이 배열을 이용해 a부터 b까지의 구간 합을 구한다고 하면,

pSum[b]는 arr[0]부터 arr[b]까지의 합이고

pSum[a]는 arr[0]부터 arr[a]까지의 합이니,

PSum[b] - pSum[a-1]의 값이 a부터 b까지의 구간 합이 된다.

 

 

코드

import java.util.StringTokenizer

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = Integer.parseInt(br.readLine())
    var tk = StringTokenizer(br.readLine())
    val sum = IntArray(n+1){0}
    for(i in 1 .. n){
        sum[i] = sum[i-1]+ Integer.parseInt(tk.nextToken())
    }

    val m = Integer.parseInt(br.readLine())
    for(i in 0 until m){
        tk = StringTokenizer(br.readLine())
        val (a,b) = List(2){Integer.parseInt(tk.nextToken())}
        write("${sum[b]-sum[a-1]}\n")
    }
    close()
}