[백준/BOJ] 17390번: 이건 꼭 풀어야 해!

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개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

해설

비내림차순이기 때문에 그냥 오름차순으로 정렬하여 문제를 풀었다.

반복문을 통해 계산을 했을 때 시간초과가 났다.

 

이를 해결하기 위해 투포인터 알고리즘을 사용하였다.

미리 각 인덱스까지의 합을 구하고 범위가 주어졌을 때 그 이전의 범위를 빼는 것이다.

 

문제의 예시인 2 5 1 4 3을 예로 보자.

정렬을 하면 1 2 3 4 5가 되고 각 인덱스의 합은 1 3 6 10 15가 된다.

만약 2 4의 범위가 주어졌다면 인덱스 4까지의 합인 10에서 범위 밖인 인덱스1인 1을 빼주면 된다.

 

이와 같은 방법으로 다중 반복문을 쓸 것을 단일 반복문으로 문제를 해결하여 시간을 줄일 수 있다.

소스 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    val (n, q) = readLine().split(" ").map { it.toInt() }
    val arr = IntArray(n + 1)
    arr[0] = 0
    val point = IntArray(n + 1)
    val st = StringTokenizer(readLine())
    for(i in 1 .. n) arr[i] = st.nextToken().toInt()
    arr.sort()
    point[0] = 0
    for(i in 1 .. n) point[i] = point[i-1] + arr[i]
    repeat(q) {
        val (start, end) = readLine().split(" ").map { it.toInt() }
        val ans = point[end] - point[start - 1]
        sb.append(ans).append("\n")
    }
    println(sb.toString())
}