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

🚀 문제 핵심

N개의 수가 주어졌을 때, 특정 구간 $(i, j)$의 합을 구하는 문제입니다.
단순해 보이지만 질의(M)의 횟수가 최대 10만 개라는 점이 핵심입니다.

💡 왜 누적 합(Prefix Sum)인가?

처음 문제를 접하면 '루프 돌려서 더하면 되지 않나?'라고 생각할 수 있습니다. 하지만 시간 복잡도를 따져보면 결과는 달라집니다.

• 단순 반복: $M$번의 질의 $\times$ 최대 $N$번의 덧셈 = $O(M \times N)$
• 연산 횟수: $100,000 \times 100,000 = 10,000,000,000$ (100억 번)
• 결과: 1초라는 시간 제한 내에 절대 통과할 수 없습니다. (Time Limit Exceeded)

따라서 질의가 들어올 때마다 계산하는 것이 아니라, 미리 합을 구해두고 꺼내 쓰는 $O(1)$의 전략이 필요합니다.

---

🏗️ 설계: 구간 합의 원리

누적 합 배열 $S$를 다음과 같이 정의합니다.

• $S[i]$ = 1번부터 $i$번까지의 합

이렇게 미리 배열을 만들어두면, 어떤 구간 $(i, j)$의 합도 단 한 번의 연산으로 구할 수 있습니다.

• 공식: $Sum(i, j) = S[j] - S[i - 1]$

---

💻 구현 코드 (Java)

이번 문제는 설계 단계에서 자료형(long)과 인덱스(1-based)를 고려하여 한 번에 통과(One-shot AC)하는 것을 목표로 했습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        // 빠른 입출력을 위해 BufferedReader 사용
        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. 누적 합 배열 생성
        // n+1 크기로 선언하여 i-1 인덱스 접근 시 예외 방지 (1-based index)
        long[] prefix = new long[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            // S[i] = S[i-1] + 현재값
            prefix[i] = prefix[i - 1] + Long.parseLong(st.nextToken());
        }

        // 2. 질의(M) 처리
        StringBuilder sb = new StringBuilder();
        for (int q = 0; q < m; q++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());

            // 공식: S[j] - S[i-1]
            sb.append(prefix[j] - prefix[i - 1]).append('\n');
        }

        // 결과 일괄 출력
        System.out.print(sb);
    }
}

✅ Tip: 구현 포인트

1. Index 0의 활용: prefix[0]을 0으로 비워두면, 구간의 시작점 $i$가 1일 때도 별도의 if문 없이 prefix[1] - prefix[0]으로 처리가 가능합니다. 코드가 훨씬 간결해지죠.
2. long 타입 추천: 누적합은 숫자가 커질 가능성이 높습니다. 습관적으로 long을 사용하여 오버플로우를 방지하는 것이 좋습니다.
3. StringBuilder: 출력 양이 많을 때는 System.out.println을 반복하기보다 StringBuilder로 모아서 한 번에 출력하는 것이 성능상 유리합니다.

---

🎯 마치며

누적 합은 알고리즘의 기초지만, 이후 배우게 될 2차원 구간 합, 나머지 합, 더 나아가 세그먼트 트리의 모태가 되는 아주 중요한 개념입니다. '미리 계산해둔다'는 메모이제이션의 기초를 다지기에 아주 좋은 문제였습니다.