[백준 - 11659/ Java] 구간합 구하기

문제를 풀기 전에 우선 구간합을 구하는 방법을 알아야한다.

하지만 또! 구간합을 구하기 전에 합 배열을 만들줄 알아야 한다. ㅎㅎ

알아야하는 이유는 다음과 같다.

반복문으로 해당 문제를 풀었을때에는 시간 초과가 발생했다.

•  주어진 질의의 개수가 최대 10만개이다.
• 수의 개수도 최대 10만개이다.
• 최악의 경우에는 10만개의 수를 가진 배열안에서 10만번의 질의를 반복문을 돌려야한다. 이때 반복문을 통한 시간복잡도 O(n^2)로는 해결할 수 없다.
• 이 때 구간합으로 문제를 해결한다면 누적배열합을 생성하는데 O(N)이 들고 M번 반복하므로 O(N+M)의 시간복잡도를 갖는다.
• 해당 문제는 1초안에 풀어야하는데 구간합 알고리즘을 모른다면 반복문으로 통해 최악의경우 1억회이상의 연산을 하기때문에 시간내에 풀기 힘들것이다.

 

합 배열이란?

예를 들어 5개를 넣을 수 있는 배열이 있다. 이 배열을 합 배열로 만든다고 하면 아래처럼 만들수있다.

A배열은 배열에 값을 순서대로 넣은 것

S배열은 인덱스가 지남에 따라 이전 인덱스에 있는 값들을 합산한것이다.

공식으로 한다면 이와 같다.

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

S[i-1] = 이전 인덱스들의 합

A[i] = 현재 인덱스의 값

 

 

이러한 합 배열을 만들었다면 구간합을 만들어 볼 수 있다.

구간합의 공식은 다음과 같다.

intervalSum = s[end] - s[start-1]

그림으로 나타내면 이와 같다.

원하는 구간의 합을 구하기 위해서는 해당 요구 구간의 마지막에서 해당 요구 구간 첫영역의 이전 영역을 빼는것이다.

예를 들어, 값이 인덱스마다 1개씩 증가하는 배열이 있다. [0,1,2,3,4,5] 

이 배열을 합 배열로 만든다면 이렇게 나온다. [0,1,3,6,10,15]

1~4번째 구간의 합을 구하고 싶다면  4번째 값에서 0번째값을 뺀다. 10-0 =10이다. (0+1+2+3+4 =10 )

2~3번째 구간의 합을 구하고 싶다면 3번째 값에서 1번째 값을 뺀다. 6-1= 5다. (2+3=5)

이러한 알고리즘을 적용하여 코드를 구현하면 다음과 같다.

 

package Array;

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

public class ArrayP11659 {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int suNo = Integer.parseInt(st.nextToken());
        int quizNo = Integer.parseInt(st.nextToken());
        //덧셈이나 곱셈이 많을때는 습관적으로 long[]만들어주는게 좋다.
        long[] S = new long[suNo+1];

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

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