[백준] 구간 합 구하기 4 JAVA

728x90

반응형

[백준] 구간 합 구하기 4

11659번: 구간 합 구하기 4 (acmicpc.net)

---

접근

• 누적합

---

풀이

문제만 봐선 브론즈 정도의 문제가 왜 실버에 있는가 했다.

Scanner 말고 BufferedReader를 사용하라고 해둔 문제인가 싶어 BufferedReader와 BufferedWriter로 풀어봤다.

 

입력받은 값들을 배열에 넣고 반복문을 돌려 합을 구했더니 시간초과가 났다.

그래서 수가 많아지면 배열 접근에 시간이 많이 드는가 싶어 map에 넣어 돌려봤지만 또 시간 초과가 났다.

직접 합을 계산하라는 문제가 아닌 거 같았다.

 

그렇다 이 문제는 누적합을 이용하라는 문제였던 것이다.

누적합은 주로 구간합이나 부분합을 계산하는 데 사용된다.

 

누적합을 사용하지 않을 경우 시간 복잡도는 테스트 케이스의 수인 M번의 반복문 아래 구간 최대 N번의 반복문이 또 들어가기 때문에 O(N * M)으로 최악의 경우 10,000,000,000의 반복이 수행된다. 

하지만 누적합을 사용할 경우 반복 없이 상수 시간을 가지는 연산만 발생이 되므로 O(N + M)의 복잡도를 가지고 최악의 경우 200,000의 반복을 가진다.

0 개수의 차이만 해도 어마어마한 차이가 나며 누적합을 사용하지 않을 경우 문제에서 요구하는 시간을 만족할 수 없다.

 

이번 문제에서는 누적합을 사용해 입력받는 N개의 수들을 dp와 같은 방식으로 더해진 배열을 만들어 두고 구간의 값을 계산한다.

String[] line = br.readLine().split(" ");
int[] arr = new int[n + 1];

int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
	arr[i] = Integer.parseInt(line[i - 1]);
	prefixSum[i] = prefixSum[i - 1] + arr[i];
}

인덱스 관리를 편하게 하기 위해 배열은 N값보다 크게 선언한다.

arr 배열은 입력받는 수를 담는 배열이고 prefixSum 배열은 누적합을 계산할 배열이다.

이로 인해 입력이 5 4 3 2 1이 들어왔다면

arr = {0, 5, 4, 3, 2, 1}

prefixSum = {0, 5, 9, 12, 14, 15}

의 값을 가진 배열이 완성된다.

for (int i = 0; i < m; i++) {
	String[] range = br.readLine().split(" ");
	int start = Integer.parseInt(range[0]);
	int end = Integer.parseInt(range[1]);

	int sum = prefixSum[end] - prefixSum[start - 1];

	bw.write(sum + "\n");
}

구간 계산을 위한 부분이다.

구간이 끝나는 지점의 누적합 값과 구간이 시작하는 지점의 앞의 값을 빼준다.

구간 시작점 1칸 앞의 값을 빼주는 이유는 예를 들어 구간이 3~6이라면 누적합 배열 6번지에는 1~6의 값의 총합이 들어있고 구간 밖의 값인 1,2 번지의 값이 포함된 상태이기 때문에 1,2번지의 합인 시작점의 앞 번지, 즉 2번지의 값을 빼주게 된다면 순수한 3~6번지의 구간합을 얻을 수 있다.

---

전체 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nAndM = br.readLine().split(" ");

        int n = Integer.parseInt(nAndM[0]);
        int m = Integer.parseInt(nAndM[1]);

        String[] line = br.readLine().split(" ");
        int[] arr = new int[n + 1];

        int[] prefixSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(line[i - 1]);
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        for (int i = 0; i < m; i++) {
            String[] range = br.readLine().split(" ");
            int start = Integer.parseInt(range[0]);
            int end = Integer.parseInt(range[1]);

            int sum = prefixSum[end] - prefixSum[start - 1];

            bw.write(sum + "\n");
        }


        bw.flush();
        bw.close();
        br.close();
    }
}