백준 17390 이건 꼭 풀어야 해! Kotlin (누적 합)

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

17390번: 이건 꼭 풀어야 해!

문제

숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!

욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어 버렸다!! 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 Q개나 주어진다!! (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!)

• L R: BL + BL+1 + ... + BR-1 + BR 을 출력한다.

Figure 1. 모든 참가자가 문제를 풀 수 있을 것이라고 기대하는 욱제의 표정

욱제의 질문에 답하고 함께 엠티를 떠나자!!

입력

첫 번째 줄에 수열 A의 길이 N과 질문의 개수 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 300,000)

두 번째 줄에 N개의 정수 A1, A2, ..., AN 이 공백으로 구분되어 주어진다. Ai 는 수열 A의 i 번째 수이다. (1 ≤ Ai ≤ 1,000)

세 번째 줄부터 Q개의 줄에 걸쳐 욱제의 질문을 의미하는 두 수 L, R이 공백으로 구분되어 주어진다. (1 ≤ L ≤ R ≤ N)

주어지는 모든 입력은 자연수이다.

출력

Q개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

알고리즘 분류

• 정렬
• 누적 합

풀이

누적 합 문제이다.

주어진 입력을 '비 내림차순'으로 정렬하라고 했는데, 그냥 오름차순 정렬하면 된다.

정렬한 후, 이를 누적 합으로 만들고, 주어진 questions에서 s, e를 추출해서 preSum[e] - preSum[s-1]을 출력하면 된다.

입력으로 주어진 s,e는 s와 e를 다 포함하는 구간이기 때문에, preSum[s-1]을 출력해야 s<= x <=e 구간의 합을 구할 수 있다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n,q) = getIntList()
    val input = getIntList().toIntArray()
    val questions = Array(q){ getIntList()}
    input.sort()
    val preSum = IntArray(n + 1)
    for (i in 1..n) {
        preSum[i] = preSum[i - 1] + input[i - 1]
    }
    for ((s, e) in questions) {
        write("${preSum[e] - preSum[s - 1]}\n")
    }
    close()
}