[백준/11659] 구간 합 구하기4

반응형

[문제]

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

(제한조건)

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

ex.
N = 5 / M = 3
arr = {5,4,3,2,1}
if i = 1, j=3
if i = 2, j=4
if i = 5, j=5
결과
12 / 9 / 1

 

 

[풀이]

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

public class Main{
    public static void main(String[] args) throws IOException{
        //Scanner sc = new Scanner(System.in);// Scanner보다 BufferedReader가 더 빠름
        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()); // 합을 구해야 하는 횟수
        
        long[] arr = new long[n+1]; // n개의 수 담을 배열 > 바로바로 구간합으로 배열 정리

        st = new StringTokenizer(br.readLine());
        
        for(int i = 1; i <= n; i++){ // n개의 수 담을 배열에 수 담기
            arr[i] = arr[i-1]+Integer.parseInt(st.nextToken()); // 합 배열에 또 담기
        }

        for(int x=0;x<m;x++){ //i, j 받아서 그 사이 구간 합 구하기
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken()); // i번째 구간
            int j = Integer.parseInt(st.nextToken()); // j번째 구간
            
            System.out.println(arr[j]-arr[i-1]);
        }
    }
}

 

[개념정리]

*구간 합 공식

int[] A = {1,2,3,4,5};
int[] S = new int[A.length];

//구간합 공식
S[i] = S[i-1] + A[i];

if i번째부터 j번째까지의 구간 합
int sum = S[j] - S[i-1];