백준 11659_구간 합 구하기 4_JAVA

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

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

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());

        // 인덱스를 신경쓰지 않기 위해 +1
        // 설명) 2번째 숫자를 구해라고 했을때 인덱스도 2로 맞추기 위해서!
        // 합 배열
        long sumArray[] = new long[n+1];

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

        // i가 1부터 시작하는 이유는 위에 합 배열에서 인덱스를 신경쓰지 않기 위해 1부터 넣기 때문
        for(int i=1; i<=n; i++) {
            sumArray[i] = sumArray[i-1] + Integer.parseInt(st.nextToken());
        }

        // 문제 수 만큼 반복
        for(int q=0; q<m; q++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());

            System.out.println(sumArray[j] - sumArray[i-1]);
        }
    }
}

 

회고

- 처음에는 그냥 무식하게 매번 모든 걸 더해줘서 구하는 방식을 선택했어서 시간초과가 났다.

- 검색 후 구간 합(합 배열) 알고리즘을 알게 되었고 합 배열을 만들어 합 배열에서만 계산을 진행하였더니 풀렸다.

- java로 전향한지 얼마 되지 않아서 그런지 입력 받는게 너무 힘들다.