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

입출력 예시

Input
5 3
5 4 3 2 1
1 3
2 4
5 5
Output
12
9
1

문제 풀이

---

이 문제는 구간 합 알고리즘을 활용해 합배열을 만들어서 풀어야 한다.

먼저 n개의 수들의 합배열을 만들어보자.

합배열 만들기

n개의 수를 5,4,3,2,1 라고 한다면, 합배열은 각 수의 합을 더해 나가면 5,9,12,14,15 이다.
그렇다면 합배열을 만드는 과정을 코드로 작성해보자.

int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] sum = new int[n+1];

문제 요구사항대로 n과 m을 입력받고 n개의 수를 입력받아 sum 배열에 담을 것이다.
이때, sum 배열의 경우 n+1의 크기를 가지고 있다.

합배열의 크기는 왜 n+1인가?
문제에서 i와 j를 보면 [1,3], [2,4], [5,5] 등 배열에서의 인덱스+1 로써 표현되고 있다.
합배열에 0,1,2,3,4 인덱스가 아닌 1,2,3,4,5라는 인덱스로 접근하기위해 sum[0]은 0인채로 두고, 1,2,3,4,5 인덱스 자리를 초기화해야 한다.

이제 sum배열의 1,2,3,4,5 인덱스에 주어진 수들을 더한 누적값으로 채워나가야한다.
합배열을 sum, 주어진 수배열을 N이라고 했을 때, 합배열을 만드는 공식은 아래와 같다.

• sum[i] = sum[i-1] + N[i]

예를 들어 N=[5,4,3,2,1]이라고 한다면,

sum[1] = sum[0]+N[1] = 0+5 = 5
sum[2] = sum[1]+N[2] = 5+4 = 9
sum[3] = sum[2]+N[3] = 9+3 = 12
sum[4] = sum[3]+N[4] = 12+2 = 14
sum[5] = sum[4]+N[5] = 14+1 = 15

위와 같은 과정으로 합배열이 이루어짐을 알 수 있다.
그러면 합배열을 만드는 코드를 작성해보자.

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

위의 합배열 공식을 그대로 적용하여 합배열인 sum = [5,9,12,14,15]를 만들 수 있다.

i부터 j까지의 구간 합 구하기

합배열을 만들었으니 i와 j를 입력받고 i번째 수부터 j번째 수까지의 합을 구해야 한다.
i번째 수부터 j번째 수까지의 구간 합을 구하는 공식은 아래과 같다.

• 구간 합 : sum[j] - sum[i-1]

예를 들어 N=[5,4,3,2,1]이고, i가 1, j가 3이라면 5+4+3인 12를 구해야한다. 공식을 적용해보자.

sum = [0,5,9,12,14,15]
sum[3]-sum[0] = 12-0 = 12

또 i가 2, j가 4일 때라면 4+3+2인 9를 구해야 한다.

sum[4]-sum[1] = 14-5= 9

위와 같이 합배열과 구간합이 연관되어 있음을 알 수 있다.
구간 합을 구하는 공식을 코드로 작성해보자.

for(int idx=0; idx<m; idx++) {
    st = new StringTokenizer(br.readLine());
    int i = Integer.parseInt(st.nextToken());
    int j = Integer.parseInt(st.nextToken());
    bw.write(sum[j]-sum[i-1]+ "\n");
}

i와 j의 입력횟수 m만큼 순회하며 i와 j를 입력받고 합배열에서 구간 합 공식을 이용해 구간 합을 구하였다.

작성코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
        }
        for(int idx=0; idx<m; idx++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            bw.write(sum[j]-sum[i-1]+ "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 구간 합과 합배열의 활용법을 제대로 공부할 수 있었고, 구간 합을 빠르게 구해야 할때 쉽게 사용할 수 있다고 느꼈다.