[Java] 백준_구간합구하기_11659

문제

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

 

입력

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

 

출력

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

 

분석

데이터 갯수는 10만 개이고, 구간 합을 구해야 하는 횟수도 최대 10만 번이다. 즉 최악의 경우 시간 복잡도는 O(n^2). 연산이 10만^2번, 100억이 되어 100초가 걸린다. 제한시간이 0.5초이므로 단순히 이중 for문으로 문제를 풀 수 없다. 이 문제를 풀기 위해서는 구간합 알고리즘을 이용해야 한다. 여러 번 구간 합을 구할 경우에는 매번 중복되어 구간 합을 구하기보다 미리 합 배열을 이용해서 구간 합을 구하면 좋다. a = { 5, 4, 3, 2,1}일 때합 배열은 S={5, 9, 12, 14, 15}가 된다. 합 배열은 S[i] = S[i-1] + arr[i]를 통해 구할 수 있다. 합 배열을 구한 후 구간 a, b의 합은 S[b] - S[a-1]과 같다.이중for문을 사용하지 않고 for문을 한 번만 사용하기 때문에 구간합 알고리즘을 이용하면 시간 복잡도는 O(N^2)에서 O(N)으로 낮출 수 있다.

 

소스코드

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

/*
* https://www.acmicpc.net/problem/11659
* 1.문제 분석
* 구간 합 문제. 구간 합을 여러번 구해야 되는데 제한 시간은 0.5초로 짧다. 따라서 무조건 구간 합 알고리즘을 사용해야 한다.
* 데이터 크기: 100,000이고 최악의 경우 O(N^2)이 되어 100억번 연산을 하게 되어 100초가 걸릴 수 있다.
* 제한시간:0.5초 제한 시간이 적으니 BufferdReader와 StringBuilder를 이용한다.
* - 제약사항: N=1, M=1일때
*
* 2.수도 코드
* - 데이터의 갯수와 질의 갯수를 입력받는다.
* - 배열의 요소 값을 입력받는다.
* - 합배열을 구한다.
* - 질의 갯수만큼 반복한다.
*   - 구간 i,와j를 입력받는다.
*   - 해당 구간의 합을 StringBuilder에 기록한다.
* - sb를 출력한다.
* */
public class 구간합구하기_11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N+1];
        int[] sum = new int[N+1];

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

        for (int i=1; i<=N; i++) {
            sum[i] = sum[i-1] + arr[i];
        }

        int i,j,result;
        for (int k=0; k<M; ++k) {
            st = new StringTokenizer(br.readLine());
            i = Integer.parseInt(st.nextToken());
            j = Integer.parseInt(st.nextToken());

            result = sum[j] - sum[i-1];

            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

결과