[알고리즘] 11659번

오늘 풀어볼 문제는 백준 11659번 문제 "구간 합 구하기 4" 이다.

이 문제는 실버3 문제이고 구간 합 구하기 문제이다.

문제

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

입력

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

출력

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

📌첫 번째 도전📌
구간 합을 구하면 되니깐 현 인덱스를 입력 받은 수 + 전 인덱스 해서 넣는 방법이 어떨까? 라는 생각을 했다.
0 5 4 3 2 1 -> 0 5 9 12 14 15 이렇게 배열에 넣는 것이다.
그럼 구간의 합을 구할 때는 array[end] - array[start - 1] 해주면 구간의 합이 출력되게 된다.

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

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

        long[] arr = new long[N+1];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i=1; i<=N; i ++) {
            arr[i] = arr[i-1] + Integer.parseInt(stringTokenizer.nextToken());
        }

        for(int i=0; i<M; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int start = Integer.parseInt(stringTokenizer.nextToken());
            int end = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(arr[end] - arr[start - 1]);
        }

    }
}

성공적으로 출력이 됐다 ㅎㅎ 원래 처음엔 방법을 이중 for문을 이용해서 일일 두 번 계산하는 방법으로 갈까 싶었는데, 너무 비효율적이라는 판단이 들어서 배열에 수를 넣는 방법을 꼬아서 생각했더니 훨씬 간단해졌다.

[문제 출처] https://www.acmicpc.net/problem/11659