[JAVA] 백준 11660번 : 구간 합 구하기 4

https://www.acmicpc.net/problem/11659
이 문제를 통해 누적합이라는 개념에 대해 처음 알게 되었다. 또한, 백준에서 늘 예외 처리를 해 왔었는데 예외 처리에서 잘못되면 런타임 에러가 발생하기 때문에 예외처리를 하는 것이 꼭 좋은 것만은 아니라는 사실도 알게 되었다.

누적합

0번째 index부터 N번째 index까지 탐색하면서 index=0 ~ index=N 까지의 index합
시간복잡도 : O(N)

구간합

누적합 구간간의 차이를 빼주면 됨

정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()); // 사용자에게 입력받음

        int N = Integer.parseInt(st.nextToken()); //줄의 개
        int M = Integer.parseInt(st.nextToken()); // 합을 구해야 하는 횟수
        int[] arr = new int[N + 1]; // 누적합을 저장할 배열. index자리에 i,j가 들어가 계산을 수행
        StringBuilder sb = new StringBuilder();


        st = new StringTokenizer(br.readLine()); // 새 입력을 받음
        for (int c = 1; c <= N; c++) { // index가 1부터 N까지
            arr[0] = 0;
            arr[c] = arr[c - 1] + Integer.parseInt(st.nextToken());// 이전까지의 합 + 입력받은 것을 쪼갠 것을 기준으로 현재의 값
        }

        for (int a = 0; a < M; a++) {
            st = new StringTokenizer(br.readLine()); // 새 입력을 받음
            int i = Integer.parseInt(st.nextToken()); // 시작
            int j = Integer.parseInt(st.nextToken()); // 끝
            sb.append(arr[j]-arr[i-1]).append("\n");
        }
        System.out.println(sb);
    }
}