[TIL] 자바 알고리즘 코딩 테스트 개념 : 구간 합 구하기

합 배열
S[i] = S[i-1] + A[i]

 

구간 합 

S[j] - s[i-1]

---

수 N개가 주어졌을 때 i번째 수에서 j번째 수까지의 합을 구하는 프로그램

 

입력

1번째 줄에 숫자의 개수 N(1<=N<=100,000), 합을 구해야하는 질의 횟수 M(1<=M<=100,000)

2번째 줄에 N 개의 수

3번째 줄부터는 M개의 줄에 합을 구해야 하는 구간 i와 j

 

출력 예제

5 3 // 데이터의 개수, 질의 개수 5 4 3 2 1 // 구간 합을 구할 대상 배열 1 3 // 구간 1~3 2 4 5 5

12 9 1

 

 

코드

import java.util.*;
public class main {
	public static void main(String[] args){
    
    	// 받는 데이터가 많을 때에는 Scanner보다 BufferedReader 사용
    	BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()); // 토큰으로 값 분리해서 사용
        
        int sNo = Integer.parseInt(st.nextToken()); // 숫자 개수
        int qNo = Integer.parseInt(st.nextToken()); // 질의 개수
        
        long[] S = new long[sNo + 1];
        st = new StringTokenizer(bf.readLine); // 새로운 입력을 받기 위해 객체 생성
        for(int i = 1; i <= sNo; i++) { // i = 1 주의
        	S[i] = S[i-1] + Integer.parseInt(st.nextToken()); // 합 배열 생성
        }
        for(int q = 0; i <= qNo; q++) {
        	st = new StringTokenizer(bf.readLine);
            int i = Integer.parseInt(st.nextToken()); // 구간 i
            int j = Integer.parseInt(st.nextToken()); // 구간 j
            System.out.println(S[j] - S[i-1]); // 구간 합
        }
        
    }
}