[백준 11659번] 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

N개의 숫자가 주어졌을 때, 인덱스 i에서 j까지의 합을 구하는 문제

시간제한 : 1초

1 ≤ N ≤ 100,000

1 ≤ M ≤ 100,000

1 ≤ i ≤ j ≤ N

2. 나의 방식대로 문제를 재정의 하자.

구간합을 구하는 문제

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

구간합을 구해야 한다.

값을 하나씩 더하는 경우 시간복잡도가 n^2이기 때문에 100,000 * 100,000으로 1초가 넘는다.

 

그렇기 때문에 주어진 리스트를 for문을 통해 1부터 값을 저장하는데

ary[0] = 0으로 설정한 후, ary[1] 부터는 누적인 값을 저장한다.

 

이후에 3번 인덱스의 값을 알고싶으면 ary[3]-ary[2]

3~5 인덱스합의 값을 알고싶으면 ary[5]-ary[2] 이런식으로 값을 쉽게 유추할 수 있다.

 

4. 어떻게 계산할 것인가?

1) 입력

bufferedReader

StringTokenizer

 

2) 시간 복잡도 계산

O(n)

 

5. 주의할 점은 무엇인가?

시간초과에 주의하기

 

6. 풀이 과정

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

public class q11659 {

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

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

    Integer start;
    Integer end;
    for (int i = 1; i <= M; i++) {
      st = new StringTokenizer(br.readLine());
      start = Integer.parseInt(st.nextToken());
      end = Integer.parseInt(st.nextToken());

      System.out.println(ary[end] - ary[start-1]);

      
    }

    br.close();
  }

}

 

7. 개선점

누적합 개념을 처음 적용해보기 때문에 잘 알아두기!