[백준 P11659] 구간 합 구하기 4 자바 Java

구간 합 구하기 4

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

11659번: 구간 합 구하기 4

 

입력값

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

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

5 3
5 4 3 2 1
1 3
2 4
5 5

 

출력값

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

12
9
1

 

알고리즘

N, M이 100,000 이하의 수이다. 그래서 매 순간마다 새로운 구간 합을 구해서 출력한다면 시간초과가 나기 쉬운 문제이다. 따라서 이 문제는 구간합을 누적합으로 풀어야 한다.

 

누적합은 특정 순서의 원소를 배열에 저장할 때 그냥 저장하는 것이 아니고, 그 전 인덱스의 원소와 합해서 저장하는 방식이다. 예를 들어 1, 2, 3, 4, 5를 저장한다고 가정해보자.

 

원래는 아래와 같은 방식으로 배열에 원소를 저장했을 것이다.

1

2

3

4

5

 

이를 누적합으로 바꾸면 다음과 같다.

1

3

6

10

15

 

누적합 배열을 구성한 이후에 범위를 받아오면 단 한번의 뺄셈으로 두 범위 사이의 합을 구할 수 있다. 예를 들어 2, 4 범위의 원소의 합을 구한다고 가정해보자.

 

원래 배열 상태에서 2번째 인덱스의 값은(문제에서는 1을 첫 번째 숫자로 가정한다.) 2, 4번째 인덱스의 값은 4이다.

1

2

3

4

5

 

따라서 2 + 3 + 4 를 계산한 9가 정답으로 나온다.

 

누적합의 관점에서 계산해보자. 우리가 구해야 하는 수는 2 + 3 + 4의 결과 값이다.

현재 배열에 들어있는 숫자들은 다음과 같다.

1	3	6	10	15
1	1 + 2	1 + 2 + 3	1 + 2 + 3 + 4	1 + 2 + 3 + 4 + 5

 

따라서 누적합 배열의 4번째 인덱스 (1 + 2 + 3 + 4) 와 1번째 인덱스 (1)를 빼면 우리는 2 + 3 + 4의 값을 얻을 수 있다.

이처럼 구간의 길이와 상관없이 2번의 조회와 1번의 연산으로 빠르게 구간합을 구할 수 있어 누적합을 사용한다.

 

코드

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

public class Main {
    public static int N, M;
    public static int start, end;
    public static int[] numList;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());
            System.out.println(numList[end] - numList[start  - 1]);
        }
    }
}