백준 No.17390 - JAVA

문제

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

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

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

 

5 6
2 5 1 4 3
1 5
2 4
3 3
1 3
2 5
4 5

 

풀이

입력만 보고 바로 손으로 계산해보니 해당 구간에 대한 합을 구하는 것이길래 그대로 코드로 짰더니 12퍼에서 시간초과나서 틀렸다.

일단 시간초과코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int A = Integer.parseInt(st.nextToken()); //수열의 길이
        int B = Integer.parseInt(st.nextToken()); // 질문의 개수

        int arr[] = new int[A+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= A ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        for (int i = 0; i < B ; i++) {
            st = new StringTokenizer(br.readLine());

            int temp = 0;

            int L = Integer.parseInt(st.nextToken());
            int R = Integer.parseInt(st.nextToken());

            for (int j = L; j <= R ; j++) {
                temp += arr[j];
            }
            sb.append(temp).append("\n");
        }
        System.out.println(sb.toString());


    }
}

 

그래서 시간초과를 줄이려고 생각해보니 미리 모두 더한 값을 배열에 저장하는 방법이 있어 구현했더니 통과했다.

정답이다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int A = Integer.parseInt(st.nextToken()); //수열의 길이
        int B = Integer.parseInt(st.nextToken()); // 질문의 개수

        int arr[] = new int[A+1];
        int temp[] = new int[A+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= A ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);


        for (int i = 1; i <= A ; i++) {
            temp[i] = temp[i-1] + arr[i];
        }

        for (int i = 0; i < B ; i++) {
            st = new StringTokenizer(br.readLine());


            int L = Integer.parseInt(st.nextToken());
            int R = Integer.parseInt(st.nextToken());


            sb.append(temp[R] - temp[L-1]).append("\n");
        }
        System.out.println(sb.toString());


    }
}