백준 11659. 구간 합 구하기4

문제 11659. 구간 합 구하기4

문제

수 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

풀이

이전 포스트에서 알려준 대로 합 배열을 생성하여서 구간 합을 구해내면 된다.
구간 합인 문제를 알면서도 처음 접근할 때 for문으로 구간 별 합을 구해야겠다고 생각했었다. 바보다. 아래가 안좋은 코드이다.

for(int i = 0; i < m; i++) {
	stk = new StringTokenizer(br.readline());
    int first = Integer.parseInt(stk.nextToken());
    int second = Integer.parseInt(stk.nextToken());
    
    long sum = 0;
    for (int j = first; j <= second; j++) {
		sum += arr[j];
        }
    
    System.out.println(sum);
    }

위 코드도 정상작동할 것 같은데 왜? tle가 나는걸까?
우리는 문제에서 제시한 제한을 항상 눈여겨봐야한다. 제한 신경안쓰고 코딩할거면 모든 코드를 어떻게든 짤 수 있을 것이다.

m이 최대 100,000이므로 첫번째 for문은 최대 10만번 반복할 수 있겠다는 생각을 해야한다. 그리고 두번째 for문의 first = 1, second = 100,000이 되는 경우 이 또한 최대 10만번 반복할 수 있다.

이중첩 for문이므로 100,000 x 100,000 = 1억번이 최대 반복횟수가 된다.

1억번의 연산을 보통 1초라고 생각하기 때문에 0.5초의 문제의 시간 제한 내에 이뤄질 수 없다.

그러므로 이 문제는 저 부분을 구간 합으로 해결해야 한다.

풀이코드 java

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

public class boj11659 {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        long[] sum = new long[n+1];
        stk = new StringTokenizer(br.readLine());
        for (int i = 1; i < n+1; i++) {
            sum[i] = sum[i - 1] + Integer.parseInt(stk.nextToken());
        }

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(stk.nextToken())-1;
            int second = Integer.parseInt(stk.nextToken());

            sb.append(sum[second] - sum[first] + "\n");

        }

        System.out.println(sb.toString());


    }
}