[JAVA] 백준 11659 누적합

11659번: 구간 합 구하기 4

문제

N까지의 수가 주어졌을 때 구간의 합을 구하는 문제이다.

풀이

문제를 해결하기 위해 구간합을 구해야 한다.

구간합은 다음과 같이 만든다.

int[] array = new int[size+1]
for(int i=1; i<size+1; i++){
    array[i] = array[i-1] + sc.nextInt();
}

0번 인덱스는 자동으로 0값이 들어가게 된다.

이렇게 만들어진 값은 만약 1, 2, 3, 4, 5 라는 값이 들어오면 다음과 같다.

array[0] = 0

array[1] = 1 = array[0] + value

array[2] = 3 = array[1] + value

array[3] = 6 = array[2] + value

array[4] = 10 = array[3] + value

array[5] = 15 = array[4] + value

만약 3 ~ 5의 구간합을 구하려고 한다면

array[5] - array[2] = 12로 계산할 수 있다.

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 size = Integer.parseInt(st.nextToken());
        int test = Integer.parseInt(st.nextToken());
        long[] S = new long[size+1];
        st = new StringTokenizer(br.readLine(), " ");

        for(int i=1; i<size+1; i++){
            S[i] = S[i-1] + Integer.parseInt(st.nextToken());
        }
        for(int i=0; i<test; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            System.out.println( S[end] - S[start-1] );
        }
    }
}

결과