[ 백준 17390 ] 이건 꼭 풀어야 해!

1. 문제 링크 https://www.acmicpc.net/problem/17390

17390번: 이건 꼭 풀어야 해!

2. 문제 

3. 문제 요약

 비정렬 수열을 정렬하고, 범위의 합을 출력해라

 

4. 문제 풀이

(1)  1차원 배열의 정렬

 정렬은 딱히 설명할 게 없다.

 우선 문제를 풀기 위해서 임의의 순서로 들어오는 값들을 정렬할 필요가 있다.

 N(1≤N≤300,000)개의 데이터가 들어오는 만큼 O(N²)의 정렬법은 시간초과가 분명했기에,

 O(NlogN)의 복잡도를 갖는 방법으로 정렬하고자 해서, 퀵소트를 이용해서 정렬했다. 

 

(2) 배열의 부분 합 // 메모이제이션

  정렬 후, 주어지는 Q(1≤Q≤300,000)개의 줄에 제시되는 범위의 부분 합을 출력하면 된다.

  각 줄마다 반복문을 통해서 문제를 해결하려고 하면, O(QN)의 복잡도를 갖게 되어 역시 시간초과가 분명했다.

  그래서 각 범위에 대해서 미리 계산해두고 저장해둔 뒤, 필요한 범위를 바로바로 출력하는 방식을 쓰기로 했다.

 

(3) DP의 응용

 S[ a, b ] 를 배열의 닫힌 구간 [ a, b ]에서의 부분 합이라고 한다면, 마치 적분처럼

 S[ a, b ] = S[ 1, b ] - S[ 1, a-1 ] 과 동일하다.

 따라서, int[] sum을 선언하여, sum[i] 는 1번부터 i번까지의 합이라고 하면,

 각 질문마다 S[a,b] = sum[b] - sum[a-1] 을 이용하여 바로바로 구할 수 있다.

 

5. 풀이 코드

public static void main(String[] args) throws Exception {
    stk = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(stk.nextToken());
    int Q = Integer.parseInt(stk.nextToken());
    int[] arr = new int[N + 1];
 
    stk = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++)
        arr[i] = Integer.parseInt(stk.nextToken());
 
    quickSort(arr, 1, N);
 
    int[] dp = new int[N + 1];
    for (int i = 1; i <= N; i++)
        dp[i] = arr[i] + dp[i - 1];
 
    while (Q-- > 0) {
        stk = new StringTokenizer(br.readLine());
        int head = Integer.parseInt(stk.nextToken());
        int tail = Integer.parseInt(stk.nextToken());
        int ans = dp[tail] - dp[head - 1];
        bw.write(ans + "\n");
    }
    bw.flush();
}