[Java] 백준 11659번 문제(구간 합 구하기 4)

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

 

문제설명

 

소스코드

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

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

        // n과 m을 받아옴
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 구간합 배열 생성
        int[] sumArr = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n + 1; ++i) sumArr[i] += Integer.parseInt(st.nextToken()) + sumArr[i - 1];

        // 구간 합을 통해서 값을 구함
        for (int i = 0; i < m; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            sb.append(sumArr[end] - sumArr[start - 1]).append("\n");
        }
        System.out.println(sb);
    }
}

 

설명

문제에서 수의 개수와, 합을 구해야 하는 횟수는 최대 100,000이다.

게다가 구간마다 합을 매번 계산하면 0.5초 안에 모든 구간 합 계산을 끝낼 수 없다.

이럴 때 구간 합을 이용해야 한다.

인덱스	0	1	2	3	4	5
입력값	X	5	4	3	2	1
sumArr	0	5	9	12	14	15

 

구간의 시작 인덱스를 start, 끝 인덱스를 end로 변수명을 정하면 아래와 같은 식으로 구간 합을 빠르게 구할 수 있다.

sumArr[end] - sumArr[start - 1]

• (1, 3) : sumArr[3] - [0] = 12 - 0 = 12
• (2, 4) : sumArr[2] - [4] = 14 - 5 = 9
• (5, 5) : sumArr[5] - [5] = 15 - 14 = 1