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

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

11659번: 구간 합 구하기 4

 

접근 방식)

1. 배열 값 입력받을 때, 바로 누적합 배열을 생성한다.

기본 배열(arr) → 5 4 3 2 1

누적합(sum)   → 0 5 9 12 14 15

sum[i] = sum[i - 1] + arr[i] 를 더해줘야 하니까, int[] sum 배열은 arr의 길이보다 하나 더 크게 만들었다.

 

2. 누적합을 구할 start 와 end 번호 입력받아서, 누적합 출력해준다.

인덱스 2~4까지의 누적합 

= 4까지의 누적합 - (0~1까지의 누적합)

= sum[4] - sum[2 - 1]

= sum[end] - sum[start - 1]

 

package codingTestStudy.week4;

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

public class B_11659 {
    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[] sum = new int[N + 1];     // 누적합 배열

        // 누적합 값 저장
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();
        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(sum[e] - sum[s - 1]).append('\n');
        }
        System.out.print(sb);
    }
}