백준[11659] - 구간 합 구하기 4

✏️ 문제분석

• 수의 개수와 합을 구해야 하는 횟수는 최대 10만
• 구간마다 합을 매번 계산하면 0.5초 안에 모든 구간 합계산을 끝낼 수 없음

💡 구간 합을 매번 계산하면 최악의 경우, 1억 회 이상의 연산을 수행하게 되어 1초 이상의 수행 시간이 필요함

🤚🏻 손으로 풀기

• N개의 수를 입력받음과 동시에 합 배열 생성
• 합 배열 공식
  • S[i] = S[i-1] + A[i]
  • [] : 인덱스

배열 A	5 [1]	4[2]	3[3]	2[4]	1[5]
합 배열 S	5	9	12	14	15

• 구간 합 공식
  • S[j] - S[i-1]
  • 질의(1,3) : S[3] - S[0] = 12
  • 질의(2,4) : S[4] - S[1] = 14 - 5 = 9
  • 질의(5,5) : S[5] - S[4] = 15 -14 = 1

🖊️ Sudo 코드 작성

dataNum(데이터 수), queryNum(질의 수)
for(숫자 개수만큼 반복){
	합 배열 생성하기(S[i] = S[i-1] + A[i])
}

for(질의 개수 만큼 반복하기){
	질의 범위 받기 (i ~ j)
	구간 합 출력하기 (S[j] - S[i-1])
}

🧑🏻‍💻 코드 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		
	/*
	 * 구간 합 구하기
	 * 
	 * 일반 배열 A[i]
	 * 합  배열 S[i]
	 * 
	 * 
	 * 합 배열 : S[i] = S[i-1] + A[i]
	 * 구간 합 공식 (i,j) : S[j] - S[i-1] //i 에서 j까지 구간합. 
	 * 
	 * 
	 * */
		BufferedReader bufferReader = 
				new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stringTokenizer =
				new StringTokenizer(bufferReader.readLine());
		
		//데이터개수
		int dataNum = Integer.parseInt(stringTokenizer.nextToken());
		//질의 수
		int queryNum = Integer.parseInt(stringTokenizer.nextToken());
		//합 배열 선언
		long[] S = new long[dataNum + 1];
		
		stringTokenizer = new StringTokenizer(bufferReader.readLine());
		
		//합 배열 생성
		for(int i = 1; i <= dataNum; i++) {
			S[i] = S[i-1] + Integer.parseInt(stringTokenizer.nextToken());
		}
		
		
		// 데이터마다 구간 합 구하기 
		// INPUT -> i 에서 j 까지 ( i, j ) 
		
		for(int q = 0 ; q < queryNum; q++) {
			stringTokenizer = new StringTokenizer(bufferReader.readLine());
			
			
			int i = Integer.parseInt(stringTokenizer.nextToken());
			
			int j = Integer.parseInt(stringTokenizer.nextToken());
			
			//결과출력
			System.out.println(S[j] - S[i-1]);
		}

	}

}