[BOJ] 11659번 구간 합 구하기 4 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int N, M;
    static int[] sum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sum = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            sum[i] = Integer.parseInt(st.nextToken()) + sum[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());
            int result = sum[end] - sum[start-1];
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

📄 해설

• 누적합을 사용하여 구간합을 구하는 기본 문제. 구간합 계산이 바로 접근되지 않는다면, 누적합을 구하고 누적합 배열을 출력해보길 바람
• 누적합은 sum[i] = sum[i-1] + Integer.parseInt(st.nextToken()); (이전 값들의 총합 + 현재의 값)을 계속해서 얻어지는 것으로, 입력을 받으면서 누적합을 미리 계산을 해주었음
  • 입력받으면서 안해도되고, 따로 숫자 배열 arr 을 만들어서 sum[i] = sum[i-1] + arr[i] 와 같이 구해줘도 상관은 없음
• 구간합의 경우, sum[end] - sum[start-1] (구간의 끝지점의 누적합 - 구간의 시작지점 직전까지의 누적합)을 통해 얻을 수 있음