[Java] BOJ 11659 구간 합 구하기 4

문제 

문제 링크 https://www.acmicpc.net/problem/11659

• 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
• 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다.
• 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 
• 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
• 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

아이디어

• 처음에는 반복문을 돌려서 일일이 더하면 쉽겠다고 생각했지만 그렇게 풀 경우, 시간초과가 날 것 같다는 생각이 들었다.
• 그래서 구간합을 저장할 N + 1 크기의 배열을 만들어준다.
• 숫자들을 입력받으면서 차례대로 더해주고 더한 값을 해당 배열의 순번에 저장한다.
• 예를 들어, 첫번째 값을 1 입력받으면 더하는데 쓰기위해 선언해 놓은 변수에 1을 더하고 배열 첫번째 값에 1을 넣는다.
• 두번째로 넘어가서 3을 입력받으면 위에서 썼던 변수 값 1에 3을 더해서 배열 두번째 값에 4를 넣는다. 
• 이런식으로 하나의 변수에 차례대로 입력받은 값을 더해주고 배열에 순서대로 저장한다.
• 그리고 구할 구간합의 끝점에 해당하는 배열 값에서 시작점 보다 1 작은 배열 값을 빼면 구간합이 된다.
• 처음부터 어느지점까지 구간합을 구하는 경우, 만약 배열이 0부터 시작하면 배열 범위 오류가 나므로 배열 값은 index 1부터 저장한다.

겪은 시행착오

• X

나름 쉽게 잘 풀었던 것 같다! (혹시 이것보다 더 빠르게 푸는 방법이 있는지 궁금하긴하다 ㅎ...)

코드

import java.util.*;
import java.io.*;

public class BOJ11659 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 수의 개수
        int N = Integer.parseInt(st.nextToken());

        // 합을 구해야 하는 구간 수
        int M = Integer.parseInt(st.nextToken());

        // 구간의 합을 저장할 배열
        int sum[] = new int[N + 1];

        StringTokenizer st2 = new StringTokenizer(br.readLine());

        // 구간들의 합을 구할 변수
        int s = 0;

        for(int i = 1; i <= N; i++){
            int n = Integer.parseInt(st2.nextToken());

            // 구간합을 구하기 위해서 i번째 배열에
            // i번째까지 숫자들의 합을 저장
            s = s + n;

            sum[i] = s;
        }

        // 구간합의 개수만큼 반복
        for(int i = 0; i < M; i++){
            StringTokenizer st3 = new StringTokenizer(br.readLine());

            // 시작점
            int start = Integer.parseInt(st3.nextToken());

            // 끝점
            int end = Integer.parseInt(st3.nextToken());

            // 구간의 합은 끝점까지 더한 값과 시작점 전까지 더한 값을
            // 빼는 것과 같으므로 sum[end] - sum[start - 1]을 출력
            sb.append(sum[end] - sum[start - 1] + "\n");
        }

        System.out.println(sb);
    }
}