[알고리즘] 구간 합 (부분 합)

구간 합

시간 복잡도를 더 줄이기 위해 사용하는 특수 알고리즘

S[i] = A[1] + .. + A[i]

 

 

합 배열 만드는 방법

합 배열 S[]를 만들기 위해서,

첫 번째 배열의 값은 0으로 만들고,

이후 값들은 이전 요소까지의 합 ( S[i -1] ) + 현재 요소 ( A[i] )를 더합니다.

S[0] = A[0]

S[i] = S[i-1] + A[i]

 

 

i에서 j까지 구간 합 구하는 공식

3 ~ 4까지의 합은  3+4입니다.

이때, S[4]는 1+2+3+4이기 때문에 S[2] (1+2)을 뺀다면 동일한 결과를 얻을 수 있을 것입니다.

 

즉 i부터 j번째까지 합 구하는 방법은

S[j] - S[i -1]

이라고 볼 수 있습니다.

이렇게 구간 합을 사용한다면 시간 복잡도를 효율적으로 변경할 수 있습니다.

 

 

 

코드

// bj 11659
public class Main {
	public static void main(String[] args) 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[] arr = new int[N];

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

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

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			System.out.println(S[m] - S[n - 1]); // n~m사이의 구간합 구하기

		}

	}

}

 

 

 

추천 문제

- 구간합 구하기 4

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

 

- 2차원 배열의 합

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

 

- 구간합 구하기 5

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