[Baekjoon] 9780_Range Sum Query

문제(출처: https://www.acmicpc.net/problem/9780)

---

< Range Sum Query >

 

문제 풀이 

 

누적합을 사용한다. 

 

my solution (Java)

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

public class _9780_ { // Range Sum Query

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());
		long arr[];

		for (int i = 0; i < t; i++) {
			bf.readLine();

			st = new StringTokenizer(bf.readLine());

			int n = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());

			arr = new long[n];
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
				if (j > 0) {
					arr[j] += arr[j - 1];
				}
			}

			for (int j = 0; j < q; j++) {
				st = new StringTokenizer(bf.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				if (a > 0) {
					bw.write(arr[b] - arr[a - 1] + "\n");
				} else {
					bw.write(arr[b] + "\n");
				}
			}
			bw.write("\n");
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 개수
arr : 누적합
n, q : 정수 개수, 줄 개수
a, b : 구간

 

테스트 케이스 개수를 입력받는다. 테스트 케이스 개수만큼 다음 과정을 반복한다.

 

1) 정수 개수, 줄 개수를 입력받는다.

2) 정수 개수만큼 정수를 입력받아 배열에 누적합을 구해 저장한다.

3) 줄 개수만큼 구간을 입력받아 구간의 누적합을 구해 출력한다.

---

---