문제

풀이

이해

구간에 대한 누적 합을 구하는 문제이다. 구간에 대한 각각의 수를 입력받고 합을 구할 구간을 입력받는다. 출력으로는 테스트케이스마다의 합 결과를 보인다.

예로 구간 수를 5, 4, 3, 2, 1을 입력받으면 arr[5] = {5, 4, 3, 2, 1}의 형태로 저장되고 이 때 1~3의 구간 합을 구하고 싶으면 arr[0] + arr[1] + arr[2]의 연산을 수행하면 된다. 따라서, 예시의 답은 12이다.

접근

최초에는 단순한 접근으로 생각해보았다. 말그대로 배열을 입력받고 해당 구간 인덱스를 통해 구간 합을 계산하는 것이었다. 물론 코드를 작성하기 전에도 아래와 같은 제한사항 때문에 시간초과가 예상되기는 하였다.

1 <= N <= 100000
1 <= M <= 100000

        while (M-- > 0) {
            int left = sc.nextInt();
            int right = sc.nextInt();

            int sum = 0;
            for (int i = left - 1; i <= right - 1; i++) {
                sum += arr[i];
            }
            System.out.println(sum);
        }

단순하게 left ~ right까지의 구간 수를 순회하면서 누적합을 출력하는 코드이다. 하지만 예상한대로 시간초과가 발생하였다.

따라서, 구간 합에 대한 접근을 다시 생각해보았다. 반복을 줄이기 위해서는 동적 계획법의 메모이제이션이라는 기술이 있다. 메모이제이션(memoization)이란 프로그램이 동일한 계산을 반복해야 할 때, 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하는 방식이다.

문제에서는 결국 누적 합을 구해야 하는데 이 누적 합을 미리 구하는 것으로 반복을 줄일 수 있는 것이다. 예를 들어, 누적합 배열이 있다고 가정할 때, hap[2] = hap[1] + arr[2]라는 것을 알 수 있다. 동적계획법 관점으로 생각할 때 그렇다면 n번째 누적합 점화식은 hap[n] = hap[n-1] + arr[n]이 되는 것이다.

따라서, 입력받음과 동시에 메모이제이션으로 누적합을 구하면 이후에 구간합을 구할 때의 시간복잡도는 O(1)로 줄일 수 있는 것이다.

        arr = new int[N + 1];
        arr[0] = 0;
        for(int i=1;i<=N;i++){
            int input = sc.nextInt();

            arr[i] = arr[i-1] + input;
        }

        while(M -->0){
            int left = sc.nextInt();
            int right = sc.nextInt();

            System.out.println(arr[right] - arr[left - 1]);
        }

위 코드처럼 입력과 동시에 누적합을 계산하였다.

코드

시간초과

package java_baekjoon;

import java.util.Scanner;

public class prob11659 {
    static int N;
    static int M;
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        while (M-- > 0) {
            int left = sc.nextInt();
            int right = sc.nextInt();

            int sum = 0;
            for (int i = left - 1; i <= right - 1; i++) {
                sum += arr[i];
            }
            System.out.println(sum);
        }
        sc.close();
        return;
    }
}

정답

package java_baekjoon;

import java.util.Scanner;

public class prob11659_2 {
    static int N;
    static int M;
    static int[] arr;
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        arr = new int[N + 1];
        arr[0] = 0;
        for(int i=1;i<=N;i++){
            int input = sc.nextInt();

            arr[i] = arr[i-1] + input;
        }

        while(M -->0){
            int left = sc.nextInt();
            int right = sc.nextInt();

            System.out.println(arr[right] - arr[left - 1]);
        }
        sc.close();
        return;
    }
}

결과