[BOJ] 17390: 이건 꼭 풀어야 해! (JAVA)

17390번: 이건 꼭 풀어야 해!

 

풀이

 

완탐을 돌면 당연하게 시간초과가 날 것 같았다. 300,000 x 300,000이니 당연함 ..

그래서 투포인터로 문제를 풀려고 했는데, 자꾸 오류가 나는 것 ..~ 그리고 투포인터도 결국 시간초과가 났을 것 같다.

도움을 받아 해결한 문제 ~! 누적합으로 문제를 풀면 더 쉽게 풀 수 있었다.

 

누적합을 담은 sum배열에서 0부터 R까지의 합은 sum[R]이니까,

sum[R]에서 sum[L]을 빼 준 다음 arr[L]을 더하면 정답 !

 

 

전체코드

package 백준renew;

import java.io.*;
import java.util.*;

public class 실버3_17390_이건꼭풀어야해 {
	static int arr[];
	static int sum[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		sum = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		sum[0] = arr[0];
		for(int i=1; i<N; i++) {
			sum[i] = sum[i-1]+arr[i];
		}
		
		for(int tc = 0; tc < Q; tc++) {
			st = new StringTokenizer(br.readLine());
			int L = Integer.parseInt(st.nextToken())-1;
			int R = Integer.parseInt(st.nextToken())-1;

			int ans = sum[R] - sum[L] + arr[L];
			
			sb.append(ans).append('\n');
		}
		
		bw.write(sb.toString());
		bw.close();
	}
}