[백준] 11659번 - 구간 합 구하기 4(Java)(○)

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

11659번: 구간 합 구하기 4

 

<풀이>

1. 구간합 구하는 공식을 사용하면 된다.

2. 입력합수에서 수를 입력 받을 때마다 누적합을 구해서 구간합 배열을 미리 만들자.

 

* 합 배열 공식

S[i] = S[i-1] + A[i]

 

* 구간 합 공식

A[i] ~ A[j] 사이의 합을 구하려면

S[j] - S[i-1]

 

<구현>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int N, M;
    static int A[];
    static int S[];

    public static void main(String[] args) throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new int[N+1];
        S = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            if (i > 1) {
                S[i] = S[i-1]+A[i];
            } else {
                S[i] = A[i];
            }
        }
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            sb.append(S[e]-S[s-1]).append('\n');
        }
        System.out.println(sb.toString());
    }
}