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

문제

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

11659번: 구간 합 구하기 4

시간제한 : 1초 (100,000,000)

요구 : 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합

수의 개수(N) : 100,000

합을 구해야 하는 횟수(M) : 100,000

질의마다 문제를 풀었을 때 시간제한에 걸리기 때문에 배열의 누적 합을 이용해 미리 배열을 만들어 놓고 구간합을 구하는 방향으로 잡았다.

문제 풀이

수의 개수(N) : 5
합을 구해야 하는 횟수(M) : 1
합을 구해야 하는 구간(i, j) : 2, 4

(1) 첫 번째 요소부터 구간의 최대 지점 j까지의 총합을 구한다.

(2) 첫 번째 요소부터 구간의 최소 지점인 i - 1까지의 합을 (1)에서 구한 합에서 뺀다.

 

아래의 그림은 누적합을 이용하여 각 인덱스의 배열에 적용시킨 그림이다.

누적합을 구하는 공식은 다음과 같다.

# 1차원 배열의 누적 합 구하는 공식
sumArr[i] = arr[i] + sumArr[i - 1]

이제 누적합을 적용시킨 배열을 처음 설명한 풀이 방법과 비교해보자.

처음 설명한 문제 풀이 방법은 다음과 같다.

(첫 번째 요소부터 인덱스 j까지의 합) - (첫 번째 요소부터 인덱스 i까지의 합)

위의 그림과 비교해보면 (첫 번째 요소부터 인덱스 j까지의 합)은 파란색으로 칠한 10에 해당되고, (첫 번째 요소부터 인덱스 i까지의 합)은 빨간색으로 칠한 1에 해당한다.

 

그럼 다음과 같이 공식을 정의할 수 있다.

# 1차원 배열의 구간 합 구하는 공식
result = sumArr[j] - sumArr[i - 1]

코드 1. 위의 풀이 방식을 그대로 구현

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

public class Main {
    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[] arr = new int[n + 1];
        int[] sumArr = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        // n개의 수를 입력받아 배열(arr)에 담는다.
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 배열(arr)을 이용해 누적합 배열을 구한다.
        for (int j = 1; j <= n; j++) {
            sumArr[j] = arr[j] + sumArr[j - 1];
        }
        // 누적합을 이용해 구간합을 출력한다.
        for (int k = 0; k < m; k++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());

            System.out.println(sumArr[j] - sumArr[i - 1]);
        }
        br.close();
    }
}

코드 2. 바로 누적합 배열을 생성

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

public class Main {
    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[] sumArr = new int[n + 1];

        st = new StringTokenizer(br.readLine());

        // 바로 누적합 배열을 생성
        for (int i = 1; i <= n; i++) {
            sumArr[i] = sumArr[i - 1] + Integer.parseInt(st.nextToken());
        }
        // 구간 합 출력
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int j = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            System.out.println(sumArr[k] - sumArr[j - 1]);
        }
        br.close();
    }
}