[Java] 문제 003(백준 11659번)

문제

---

구간 합 구하기 4(Baekjoon: 11659번)

 

 

풀이

---

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 suNo = Integer.parseInt(st.nextToken());
    int quizNo = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());

    // 합 배열 구하기
    long[] s = new long[suNo + 1];
    for (int i = 1; i <= suNo; i++) {
      s[i] = s[i - 1] + Integer.parseInt(st.nextToken());
    }

    // 구간 합 출력하기
    for (int q = 0; q < quizNo; q++) {
      st = new StringTokenizer(br.readLine());
      int i = Integer.parseInt(st.nextToken());
      int j = Integer.parseInt(st.nextToken());

      System.out.println(s[j] - s[i - 1]);
    }
  }
}

설명

---

개요

구간 합 이론 설명 영상을 보면 이해가 쉽다.
즉, 구간 합을 이용하지 않고, 구간마다 합을 매번 계산하면 제한 시간을 초과하게 된다.

합 배열 공식은 s[i] = s[i-1] + a[i],
i~j의 구간 합 공식은 s[j] - s[i-1],
임은 위 영상을 보면 이해할 수 있다.

해당 문제도 위 이론을 응용 없이 풀 수 있다.