[Silver III] 구간 합 구하기 4 - 11659 (누적합)

[Silver III] 구간 합 구하기 4 - 11659

문제 링크

성능 요약

메모리: 58720 KB, 시간: 1472 ms

분류

누적 합(prefix_sum)

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

풀이방법

누적합 기본 문제라 볼 수 있다.

1. 각 인덱스마다 누적한 값들을 arr배열에 저장해놓는다.

2. i~j까지의 합을 출력할 때에는 누적합을 이용하여 arr[j] - arr[i-1]을 해주면 바로 답을 구할 수 있다.

3. 예외로 i가 1일 경우, 처음부터 j까지의 합이기 때문에 그냥 arr[j] 출력

- 구간이 1 부터 시작이므로, 배열의 0번 인덱스가 시작인 것을 고려하여 풀 것.

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

public class Main {
	static int N;
	static int M;
	static int[] arr;
	static int sm;
	static int start;
	static int end;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // 수의 개수
		M = Integer.parseInt(st.nextToken()); // 합을 구해야 하는 횟수
		arr = new int[N];
		sm = 0;
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = sm + Integer.parseInt(st2.nextToken());
			sm = arr[i];
		}

		for(int i = 0; i < M; i++) {
			StringTokenizer st3 = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st3.nextToken());
			end = Integer.parseInt(st3.nextToken());
			if (start == 1) {
				System.out.println(arr[end-1]);
			} else {
				System.out.println(arr[end-1] - arr[start-2]);

			}
		}
		
	}
}