[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.util.*;
import java.io.*;

public class Main {

    public static void main(String [] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int M = scanner.nextInt();

        int [] A = new int[N+1];
        int [] sumArr = new int[N+1];

        for (int i = 1; i <= N; i++) {
            A[i] = scanner.nextInt();
            sumArr[i] = sumArr[i-1] + A[i];

        }

        for (int i = 0; i < M; i++) {
            int k = scanner.nextInt();
            int j = scanner.nextInt();

            System.out.println(sumArr[j]-sumArr[k-1]);
        }

    }
}

 

➡️ Scanner 대신 BufferReader를 사용해서 풀 수도 있다.

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 참고