백준 11659번 : 구간 합 구하기 4(Java)

🔗 문제 링크

11659번: 구간 합 구하기 4

 

---

📖 풀이 과정

 

- 누적합 유형의 문제입니다.
- 누적합 알고리즘에 대한 이해가 필요합니다.
  - 만약, 단순 for 반복문으로 해결하려한다면, 시간초과가 발생할 것입니다.
- 값을 입력받을 때부터 배열에 누적된 합을 할당합니다.
- 출력을 할 때는 (기준 인덱스) 까지의 배열값에서 (시작값 - 1) 인덱스를 이용하여 배열값을 반환합니다.

 

---

💻 코드

 

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 {
  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[] arr = new int[n + 1];
  
  st = new StringTokenizer(br.readLine()," ");
  for(int i = 1; i< n+1; i++){
   arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
  }
  
  for(int i = 0; i< m; i++){
   st = new StringTokenizer(br.readLine()," ");
   int a = Integer.parseInt(st.nextToken());
   int b = Integer.parseInt(st.nextToken());
   System.out.println(arr[b] - arr[a-1]);
  }
 }
}