자료구조 - 백준 11659

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

구간 합의 핵심 이론

합 배열 S 정의

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]  //A[0]부터 A[i]까지의 합

합 배열 S를 만드는 공식

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

구간 합을 구하는 공식

S[j] - S[i-1]  //i에서 j까지 구한 값 

---

백준 11659 - 구간 합 구하기

1. 문제 요약

1번째 줄

• N 수의 개수 N(1 <= N <= 100,000)
• M 구간 합을 구해야 하는 개수 (1 <= M <= 100,000)

2번째 줄

• N 구간 합을 구할 대상 배열

3번째 줄

• M줄에 있는 i, j 범위의 합을 구해야 함

2. 문제 분석

시간 복잡도

1. 누접합 배열 생성

• 누적합 배열 크기 = N
• 한 번 순회하면서 S[i] = S[i-1] + A[i] 계산 -> O(N)

2. M개의 쿼리 처리

• 각 쿼리(i,j)에 대해 S[j] - S[i-1] 실행
• 쿼리마다 O(1) -> O(M)

💡 총 시간 복잡도 = O(N + M)

슈도 코드

1. 숫자 개수 N 입력 받기
2. 구간 합을 구해야 하는 개수 M 입력 받기
3. 누접합 배열 S 생성 (크기 = N + 1, 초기값 S[0] = 0)
4. for(N만큼 반복) {
	4-1. 현재 수 입력 받기
	4-2. `S[i] = S[i-1] + 현재 수`로 누적합 저장
}
4. for(M만큼 반복){
	5-1. 구간 합 범위 i, j 입력 받기
    5-2. 결과 출력
}

코드 구현

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

public class No_11659 {

	public static void main(String[] args) throws IOException {

		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[] 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 a = 0; a < M; a++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			
			System.out.println(S[j] - S[i - 1]);
		}
	}
}