[백준] 11659번. 구간 합 구하기 4 (JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer sc = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(sc.nextToken());
        int M = Integer.parseInt(sc.nextToken());

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

        sc = new StringTokenizer(br.readLine());

        for(int i = 1; i < N+1; i++){
            input[i] = Integer.parseInt(sc.nextToken());
            sum[i] = sum[i-1] + input[i];
        }


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

    }
}

문제를 해결하기 위해서는 구간 합 풀이법을 알아야 한다.

 

구간 합이란 배열을 받음과 동시에 구간까지의 합을 미리 구해 하나의 배열을 추가적으로 만들어두는 것이다.

 

예를 들면, 크기가 5인 배열을 입력 받음과 동시에 0, 0+1, 0+1+2, 0+1+2+3 이런 식으로 만드는 것이다. 여기서 0+1+2+3 을 구할 때 네번 더하는 것이 아닌 이 전의 배열 값을 이용해 계산을 최적화 한다.

 

이렇게 계산하는 이유는 문제의 조건을 보면 100,000의 크기를 갖는 배열을 만들어야 하기 때문에 최악의 경우 10억번의 계산이 필요할 수도 있다. 이 과정을 생략하기 위해 하는 것이다.

 

버퍼리더와 스트링토크나이저는 아직 경험이 부족해 더 많이 사용해보고 코드르 깔끔하게 짜는 연습을 해야할 것 같다.