[BOJ-11659][구간 합] 구간 합 구하기 4 - Java

문제 바로가기

11659번: 구간 합 구하기 4

 

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 문제입니다.

prefix sum을 입력받을 때 구해서 O(N) 타임으로 구할 수 있습니다.

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

public class Main {
	public static void main(String[] args) throws Exception {
		input();
	}

	public static void input() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken());
		int[] prefixSum = new int[N+1];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 1; i <= N; i++) {
			prefixSum[i] = Integer.parseInt(st.nextToken()) + prefixSum[i-1];
		}
		
		while(M-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			System.out.println(prefixSum[j] - prefixSum[i-1]);
		}
	}
}

 

 

먼저 arry[i]~arry[j] 의 구간 합을 구하는걸 n번 해야한다면 어떻게 해야 할까여? 직관적으로 구간 합을 구하는데 O(N) 타임을 돌고 N번 반복한다면 O(N^2)가 됩니다. 좋지 않져. 이를 prefix sum을 구해서 바로 구할 수 있습니다.

 

input numbers	1	2	3	4	5	6	...
prefix sums	1	3	6	10	15	21	...

이런 식으로요. 그럼 arry[3]~arry[4] 의 값 7은 prefixSums[4] - prefixSums[2] 로 바로 구할 수 있는 것이죵.!!!

 

 

감사합니다!!