[알고리즘] 구간 합

구간 합?

• 합 배열을 이용하여 시간 복잡도를 더 줄일 수 있는 특수한 목적의 알고리즘
• 합 배열이란? 기존의 배열을 전처리한 배열로 S[i] = A[0] + A[1] + A[2] --- + A[i-1] + A[i]로 나타낼 수 있으며, S[i]는 합 배열 / A[i]는 기존의 배열이다.
  
• 합 배열 만드는 공식: S[i] = S[i-1] + A[i] / S[0] == A[0]
• 구한 합 배열로 구간 합 구하는 공식: S[j] - S[i-1] => i에서 j까지 구간 합
• EX) A[2] ~ A[5] 사이 구한 과정
  

---

실전! 문제 풀이(백준 11659)

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

class Main{
    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[] sectionArr = new int[n+1];
        sectionArr[0]=0;
        st = new StringTokenizer(br.readLine());     
        for(int i=1;i<=n;i++){
            sectionArr[i]=sectionArr[i-1]+ Integer.parseInt(st.nextToken());       
        }
        
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int start= Integer.parseInt(st.nextToken());
            int end= Integer.parseInt(st.nextToken());
           
            System.out.println(sectionArr[end]-sectionArr[start-1]);
        }        
    }        
}

얻어갈 점:

• 입력이 많으니 scanner 보단 bufferedReader로!
• 입력이 한 칸씩 띄워져서 많은 것이 들어올 때는 StringTokenizer를 이용(반환 string이니까 parseInt 해줘야함)
• 일반적으로 index는 0부터 시작하지만, 해당 문제에서는 입력 값으로 인덱스가 1부터 시작함으로, 배열 생성시 new intn이 아닌 new int[n+1]로 (0~n)만든 후 index=0인 경우는 0으로 세팅해주고, 실질적 데이터 시작 index와 끝 index를 맞춰주었다.