[알고리즘]이건 꼭 풀어야 해 ! (백준 No_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개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

---

코드

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

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

		int n = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		int A[]=new int [n+1];
		int S[]=new int [n+1];
		int sum=0;

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

		Arrays.sort(A);
		for(int i=1; i<=n; i++){
			S[i]+=A[i]+S[i-1];
		}
		
		for(int i=0; i<Q; i++){
			st=new StringTokenizer(br.readLine());
			int L=Integer.parseInt(st.nextToken());
			int R=Integer.parseInt(st.nextToken());
			System.out.println(S[R]-S[L-1]);
		}
	}
}

풀이🤩

• 먼저 수열 A를 입력 받은 뒤 문제 조건에 비내림차순(오름차순) 이라는 조건이 있으니 Arrays.sort로 정렬한다.
• 배열 S에는 A배열의 합을 계산해서 넣는다. ex) s[3]=a1+a2+a3 코드로 하면 S[i]+=A[i]+S[i-1]
• 문제의 구간을 입력 받은 후 S수열을 이용해 정답을 바로 출력한다

마무리

• 나는 첨에 int L과 R을 for문 밖에 정의했었는데 자꾸 시간초과가 나서 for문안에 넣어봤더니 바로 통과했다.. 어려운 알고리즘의 세계^_^