141. 11659(구간 합 구하기4) - 자바

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] tmp1 = br.readLine().split(" ");
		int sum = 0;

		int N = Integer.parseInt(tmp1[0]);
		int M = Integer.parseInt(tmp1[1]);

		int[] numSum = new int[N + 1];

		String[] tmp2 = br.readLine().split(" ");

		for (int k = 0; k < N; k++) {
			sum += Integer.parseInt(tmp2[k]);
			numSum[k + 1] = sum;
		}

		for (int k = 0; k < M; k++) {
			String[] tmp3 = br.readLine().split(" ");
			int i = Integer.parseInt(tmp3[0]);
			int j = Integer.parseInt(tmp3[1]);
			
			
			sb.append(numSum[j] - numSum[i-1]).append("\n");
		}
		
		System.out.print(sb);
	}
}

문제요약

구간의 부분합을 구하자

설명

정말 간단하게 생각하면 시간초과로 틀린다. (내가 그랬다 ㅎㅎ)

 

생각을 다르게하여 처음부터 누적합을 구하고 끝값에서 시작값-1 빼주는 방식으로 생각해보자.

다음과 같이 위는 입력값 밑은 누적합이다.

 

예를 들어 2와 4가 들어왔다고 하자.

2와 4의 구간의 누적합 9이다.

그럼 index 4번과 index 1번을 빼주면 되지 않을까?

맞다.

그게 정답이다.