구간 합 구하기4(BJ_S3_11659)

1. 문제 링크

 

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

 

---

 

2. 나의 코드

메모리: 58936kb
시간: 1572ms
코드 길이: 1000B
시간 복잡도 : O(N+M)
설명
- 구간 합 알고리즘이다.

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

public class BJ_11659 {

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

    public static void main(String[] args) throws IOException {
        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());
        for (int i = 1; i <= N; i++) {
            arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken()); // 합배열 만들기
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            System.out.println(arr[e] - arr[s - 1]);    // 구간 합
        }
    }
}

 

---

 

3. 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class P11659_구간합구하기 {
  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader 
      = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer 
      = new StringTokenizer(bufferedReader.readLine());
    int suNo = Integer.parseInt(stringTokenizer.nextToken());
    int quizNo = Integer.parseInt(stringTokenizer.nextToken());
    long[] S = new long[suNo + 1];
    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
    for (int i = 1; i <= suNo; i++) {
      S[i] = S[i - 1] + Integer.parseInt(stringTokenizer.nextToken());
    }
    for (int q = 0; q < quizNo; q++) {
      stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int i = Integer.parseInt(stringTokenizer.nextToken());
      int j = Integer.parseInt(stringTokenizer.nextToken());
      System.out.println(S[j] - S[i - 1]);
    }
  }
}

 

---

 

4. 배운 점

- 구간 합 알고리즘을 사용하기 위해서는 합 배열을 사용해야 한다.

- 구간 합 알고리즘은 만약 2부터 4까지의 배열의 합을 구한다면 arr[4] - arr[1] 이다.