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

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

11659번: 구간 합 구하기 4

구간 합 구하기 4 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

101082

41558

30954

39.014%

문제

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 1 복사

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 복사

12
9
1

 

<<풀이>>

 

-나의 풀이-

 

흠 일단 클래스로 따로 만들고 객체 이용해서 풀었지만 시간초과이다. 

import java.util.*;

class Sum {
    int first;
    int last;

    Sum(int first, int last) {
        this.first = first;
        this.last = last;
    }
}

class Main {
    private int[] solution(int[] arr, Sum[] brr) {
        int sum = 0;
        int[] answer = new int[brr.length];
        for(int i = 0; i < brr.length; i++){
            for(int j = brr[i].first; j <= brr[i].last; j++) {
                sum += arr[j - 1];
            }
            answer[i] = sum;
            sum = 0;
        }
        return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        Sum[] brr = new Sum[m];
        for(int i = 0; i < m; i++) {
            brr[i] = new Sum(in.nextInt(), in.nextInt());
        }

        for(int x : T.solution(arr, brr)){
            System.out.println(x);
        }

    }
}

 

 

-수정한 코드-

 

원인을 찾을 수 있었는데 이중 for문을 돌고 있는 부분에서 문제였던 것이다. 나름 짐작은 했지만, 우리는 이때 

"누적합"을 이용하는데, 이를 활용하면 이중 for문을 사용하지 않고 코드를 짤 수 있고, 시간초과에서 벗어날 수 있다.

import java.util.*;

class Sum {
    int first;
    int last;

    Sum(int first, int last) {
        this.first = first;
        this.last = last;
    }
}

class Main {
    private int[] solution(int[] arr, Sum[] brr) {
        int[] prefixSum = new int[arr.length + 1];
        for (int i = 1; i <= arr.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
        }

        int[] answer = new int[brr.length];
        for (int i = 0; i < brr.length; i++) {
            answer[i] = prefixSum[brr[i].last] -
                    prefixSum[brr[i].first - 1];
        }
        return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        Sum[] brr = new Sum[m];
        for(int i = 0; i < m; i++) {
            brr[i] = new Sum(in.nextInt(), in.nextInt());
        }

        for(int x : T.solution(arr, brr)){
            System.out.println(x);
        }

    }
}

 

누적합이란

 

 

배열에 있는 것을 처음 부터 누적한 것들을 새로운 배열 prefix라는 곳에 넣어둔다. 그리고 만약 3번째에서 5번째의 누적합을 알고 싶으면, 

23 - 9를 하면 쉽게 구할 수 있다.

 

이를 활용함으로써 이중 for문으로 시간복잡도가 O(N^2) 이 될 수 있는 것을 단순히 사칙연산 빼기로 구할 수 있게 됨으로써 시간복잡도를 O(N)으로 만들 수 있다.

 

누적합 직이네 ~~😁