#11659 : 구간 합 구하기 4

풀이방법

사용된 것:

누적합

 

2022.05.29

N+1 길이의 정수 배열을 선언한 뒤,

0번 인덱스에는 0의 값을 저장하고

그 후로 n번 인덱스에 n번째 수까지의 누적 합을 저장하는 방식으로 배열을 채운다.

 

셋째 줄부터 주어지는 숫자 i와 j에 대하여

(i번 인덱스에 저장된 수) - (j-1번 인덱스에 저장된 수) 가 정답이다.

 

코드

Java(2022.05.29)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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[] add = new int[n+1];
		st = new StringTokenizer(br.readLine());
		add[0] = 0;	//0번 요소는 0으로 설정
		//누적 합을 각 요소에 저장
		for(int i=1; i<n+1; i++) {
			add[i] = add[i-1] + Integer.parseInt(st.nextToken());
		}
		//정답 구하기
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			sb.append(add[b]-add[a-1] + System.lineSeparator());
		}
		//정답 출력
		System.out.print(sb);
	}

}