[백준 Baekjoon] 11441번 합 구하기 - JAVA

[백준 Baekjoon] 11441번 합 구하기 - JAVA

---

문제 풀이

 

이 문제를 풀기 전에 누적 합이 먼지 알아야합니다. 문제에서 구간의 합을 출력하라 하였는데, 구간의합 = 누적 합이라고 생각하시면 됩니다.

 

누적 합은 이름에서 알 수 있듯이 일정 구간의 값들을 누적한 합입니다. 누적 합을 사용하는 이유는 구하고자하는 구간의 합을 매번 구하게 되면 O(n^2)의 시간복잡도를 갖기 때문에 이번 문제와 같이 최대 100,000 개의 수들을 100,000 구간의 합을 구하면 너무 큰 비용이  발생하게 됩니다.

 

누적합을 사용하면 구간의 합을 O(n)으로 구할 수 있습니다.

 

구간의 합을 구하기 앞서 누적합을 구해줍니다.

int[] sum = new int[N + 1];

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

10	20	30	40	50
10	30	60	100	150

 

이제 구간의 합을 구할때 누적합의 값을 사용하여 시작 구간이전의 누적합을 마지막 구간까지의 누적합에서 빼면 구간의 합을 구할 수 있습니다.

 

예를 들어 [3, 5]의 구간의 합은 : (5까지의 누적합) 150 - (3이전의 누적합) 30 = 120

sum[j] - sum[i - 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));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] sum = new int[N + 1];

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

        int M = Integer.parseInt(br.readLine());
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());

            sb.append(sum[j] - sum[i - 1]).append("\n");
        }

        System.out.println(sb);
    }
}