[백준 알고리즘] 11659번: 구간 합 구하기 4 (JAVA)

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

소스코드

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

class P11659 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine()," ");
		int[] arr = new int[n];

		for (int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
        int[] dp = new int[n]; // 누적합을 저장하는 배열
        dp[0] = arr[0];

        for (int i=1;i<n;i++) {
          dp[i] = dp[i-1] + arr[i]; // 누적합 저장 
        }

		for (int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int k = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			if (k==1) {
                sb.append(dp[t-1]).append("\n");
              } else {
                sb.append(dp[t-1]-dp[k-2]).append("\n");
              }
                }
		System.out.println(sb);	
	}
}

 

풀이

★ 입력값이 최대 100,000이 들어오고, 제한 시간이 1초이기 때문에 2중 반복문을 통해 문제에서 주어진 구간의 합을 구하게 된다면 시간초과가 발생하게 됩니다. 그렇기에 입력받은 배열의 길이만큼 누적합 배열을 만든 후, 구간의 합을 누적시키는 배열을 따로 만들어준 뒤, 해결해야 합니다 !!