[문제풀이] B11659 구간합구하기4

구간합 구하기4

---

  🪅 구간합을 구할때 누적합 - 누적합을 생각해낼 수 있느냐
  🪅 누적합 배열을 만들때 index 0에 패딩까지 만들었느냐 => arr[i] + accSum[i-1];

[시간초과난 코드.java]

public class Main {
    /**
     * 백준11659 구간합구하기4
     * 입력:
     * 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 
     * 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 
     * 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
     *
     * 출력:
     * 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine(), " ");

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

        int[] arr = new int[N];
        token = new StringTokenizer(bf.readLine(), " ");
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(token.nextToken());
        }

        int[] resultArr = new int[M];
        for(int i = 0; i < M; i++) {
            token = new StringTokenizer(bf.readLine(), " ");
            int start = Integer.parseInt(token.nextToken());
            int endIdx = Integer.parseInt(token.nextToken());
            int startIdx = start - 1;
            int[] subArr = Arrays.copyOfRange(arr, startIdx, endIdx);
            int sum = 0;
            for(int j = 0, len = subArr.length; j < len; j++) {
                sum += subArr[j];
            }
            resultArr[i] = sum;
        }

        for(int i = 0, len = resultArr.length; i < len; i++) {
            System.out.println(resultArr[i]);
        }
    }
}

❓왜 시간초과가 났을까?
: N가 M은 모두 최악의 경우 100_000까지 나올 수 있다
최악의 경우에서 위 코드가 중첩for문을 돌면 연산이 1억번을 훨씬 넘긴다
때문에 1초가 넘음으로 시간초과가 된다.


📖 해결책
: 중첩for문을 사용하면 안된다
결국 구해야하는 값은 구간합이다.
구간합을 for문 한번만 돌려서 구하려면 처음 돌릴 때, 처음부터 각각 인덱스까지의 누적합을 구하고
뒤의 누적합 - 앞의 누적합 (= '구간합')을 한 번의 연산으로 구할 수 있다

[해결한 코드.java]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");

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

        int[] arr = new int[N+1]; // 0 5 4 3 2 1
        int[] accSum = new int[N+1]; // 누적합, arrSum[0]은 패딩으로 써야한다

        // arr 초기화
        token = new StringTokenizer(br.readLine(), " ");
        for(int i = 1; i < N+1; i++) {
            arr[i] = Integer.parseInt(token.nextToken()); 
        }
//        System.out.println(Arrays.toString(arr));

        // 누적합 초기화
        for(int i = 1; i < N+1; i++) {
            accSum[i] = arr[i] + accSum[i-1];
        }
//        System.out.println(Arrays.toString(accSum));

        // M번 횟수만큼
        for(int i = 0; i < M; i++) {
            token = new StringTokenizer(br.readLine(), " ");
            // 입력받고
            int startIdx = Integer.parseInt(token.nextToken());
            int endIdx = Integer.parseInt(token.nextToken());

            // 누적합 - 누적합 = 구간합
            System.out.println(accSum[endIdx] - accSum[startIdx-1]);
        }
    }
}