📣
Baekjoon에서 PASS된 코드만 업데이트합니다.
알고리즘을 먼저 풀이하는 언어(Java)가 정해져있어,
풀이 언어(Python, C++, Java)가 모두 업데이트될 때까지는 시간이 걸릴 수 있습니다.

문제 제시

---

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

문제 풀이

---

가장 처음에 생각한 건, 가장 간단한 방법입니다.
순서로 따지면,

1. 입력을 받고
2. i이상 j이하 구간을 반복하며 합해 출력한다.

였습니다. 아니나 다를까 제한 사항이 있다는 걸 잊었었죠...ㅎㅎ

깨끗하게 오류가 났습니다. 그럼 제한 사항을 조금 더 살펴보도록 하겠습니다.

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

처음에 생각했을 때의 2번이 이 제한에 걸리게 됩니다.
i부터 j까지를 반복하게 될텐데, [1 100000]인 케이스를 100000번 진행하게 된다면, 그 시간복잡도는 100000x100000 이게 되는 거죠.
네, 어마무시하게 되는 겁니다. 이 방법은 옳지 않다는 것이죠.

새로운 방법으로 찾아보겠습니다.
우선 각 구간의 합을 할 수 있어야하기 때문에, 누적합의 개념이 필요하게 됩니다.

이 특징을 정리하면 위와 같은 내용이 나오게 됩니다.
정리하게 되면,

1. 1번의 시작이 되면 누적합에서 제외할 값이 없다. (i가 1이면 0을 빼기)
2. i부터 j까지의 값을 구할 때는 j번의 값에 (i-1)번의 값을 빼면 된다.
3. 2번 특징에 따라 1번인 0번에는 0의 값을 세팅한다.

로 정리할 수 있습니다.
각 구간의 시작도 1부터 시작해야하기에 0의 인덱스는 0의 값으로 1부터의 값은 입력값으로 진행하면 됩니다.

문제 코드

---

Java

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

public class Main {

  static int N, M;
  static int[] arr;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    arr = new int[N + 1];

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

    for (int n = 0; n < M; n++) {
      st = new StringTokenizer(br.readLine());
      int i = Integer.parseInt(st.nextToken());
      int j = Integer.parseInt(st.nextToken());
      System.out.println(arr[j] - arr[i - 1]);
    }
  }
}

제출 결과

---