[백준]11659번 구간 합 구하기 4(JAVA)

0. 문제 링크

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

1. 문제 설명

1) M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지의 합 출력하기

 

2. 입출력

// input
5 3
5 4 3 2 1
1 3
2 4
5 5

// output
12
9
1

 

3. 코드

import java.io.*;
import java.util.StringTokenizer;

public class b11659 {
	static int jSum = 0;
	static int iSum = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 수의 개수
		int M = Integer.parseInt(st.nextToken()); // 합을 구해야 하는 횟수
		
		st = new StringTokenizer(br.readLine());
		int[] arr = new int[N]; // N개의 수
		for(int n = 0; n < N; n++) {
			arr[n] = Integer.parseInt(st.nextToken());
		}
		
		int[] sum = new int[N]; // 합 저장
		for(int n = 0; n < N; n++) {
			if(n == 0) {
				sum[n] = arr[0];
			} else {
				sum[n] = sum[n-1] + arr[n];
			}
		}
		
		for(int m = 0; m < M; m++) { // 합 구하기
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken())-1; // 1 <= i <= j <= N
			int j = Integer.parseInt(st.nextToken())-1;
			System.out.println(sum[j] - sum[i] + arr[i]);
		}
	}

}

 

 

실행 결과

 

4. 회고

1) 최대 100,000개의 수와 100,000개의 합을 구해야 하므로 구간 합을 이용하여 시간 초과를 해결

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b11659.java