[JAVA][Baekjoon] 11659번 구간 합 구하기 4

11659번: 구간 합 구하기 4

---

📌 접근 방법

• 구간합이란 누적합으로 구한다고 생각하면 편함!
• 배열에 값을 앞에서부터 누적시켜 저장한 후 해당 구간(i, j)의 합을 구하기 위해서는 ~j 까지의 누적합이 담긴 j번째 값에서 i-1을 빼주면 됨!

 

• 예를 들면 arr 배열에 1, 2, 4, 3, 6의 값이 있는데 2~4 구간의 합을 구하고 싶음!
• 배열에 누적합으로 1, 3, 7, 10, 16을 저장(인덱스는 1부터 시작한다)
• 4번째 값에서 2-1 번째 값을 빼주면 됨!

 

✅ PASS CODE

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

public class Main {
   public static void main(String [] args) throws IOException {
       BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(bf.readLine());

       int N = Integer.parseInt(st.nextToken());
       int M = Integer.parseInt(st.nextToken());

       long []arr = new long[N+1];
       st = new StringTokenizer(bf.readLine());
       for(int i=1; i<=N; i++){
           arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
       }

       for(int t=0; t<M; t++){
           st = new StringTokenizer(bf.readLine());
           int i = Integer.parseInt(st.nextToken());
           int j = Integer.parseInt(st.nextToken());

           System.out.println(arr[j]-arr[i-1]);
       }
   }
}

 

💡 BufferedReader 참고