[백준] 11659번 : 구간 합 구하기 - JAVA

백준 11659번 : 구간 합 구하기

 

• 문제

 

---

• 풀이방법

1. 첫 줄은 수의 개수 N, 합을 구해야 하는 횟수 M

2. 두 번째 줄은 N개의 수 

3. 세 번째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 입력된다. 

4. 합 배열을 사용하여 구간 i와 j을 구한다.

 

💡 합 배열이란?
 - 기존의 배열을 전처리한 배열을 말한다.

 

위 사진처럼 배열 A를 통해 합 배열 B를 구하려면 다음과 같다. 

 

합 배열 B의 0번째 인덱스는 배열 A의 0번째부터 0번째까지의 합,

1번째 인덱스는 배열 A의 0번째부터 1번째까지의 합 

 

즉 합 배열 B의 N번째 인덱스는 배열 A부터 N번째까지의 합을 말한다. 

B[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + ... + A[ i - 1 ] + A[ i ] 

 

합 배열을 만드는 공식
B[ i ] = B[ i - 1 ] + A[ i ]

 

합 배열의 장점

 - 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) -> O(1)로 감소한다. 

 

 

 

👉 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //
        Scanner sc  = new Scanner(System.in);
        int     N   = sc.nextInt();             // 수의 개수
        int     M   = sc.nextInt();             // 합을 구해야 하는 횟수
        //
        int[]   arry    = new int[N + 1];       // 합배열
        arry[0]         = 0;                    // 0번째 인덱스는 0으로 초기화

        for (int i = 0; i < N; i++) {
            //
            arry[i + 1] = arry[i] + sc.nextInt();
            //
        }
        //
        for (int tmp = 0; tmp < M; tmp++) {
            //
            int i = sc.nextInt();   // 합을 구해야 하는 구간
            int j = sc.nextInt();   // 합을 구해야 하는 구간
            //
            System.out.println(arry[j] - arry[i - 1]);
            //
        }
        //
    }
}

 

✍ 해설

 

변수 N은 수의 개수, 변수 M은 합을 구해야 하는 횟수를 입력받는다.

 

0번째 인덱스는 0으로 초기화 한 배열 arry에 합 배열을 만든다.

 

이 후 합을 구해야 하는 구간 i와 j가 주어지면 합배열을 통해 바로 값을 가져온다. 

 

 

❗ 구간의 합을 구하는 공식

 

예를 들어 배열 A의 A[3] 부터 A [4]까지의 구간 합의 합 배열을 구하고자 한다.

 

위 그림을 보면 A[0] + ... + A [4]에 A[0] + A[1] + A[2] 를 빼면 A[3] + A [4]가 나온다. 

즉, B[5]에서 B [2]를 빼면 구간의 합을 쉽게 구할 수가 있다.

 

i에서 j까지 구간의 합을 구하는 공식
B[ j ] - B[ i - 1 ]

 

 

 

---

[출처 : https://www.acmicpc.net/problem/11659 ]

11659번: 구간 합 구하기 4