문제 설명

N개의 수가 주어질 때,
여러 개의 구간 [i, j]에 대해

i번째부터 j번째까지의 합

을 구하는 문제이다.

---

입력

첫째 줄

N M

• N : 수의 개수
• M : 구간 합 계산 횟수

둘째 줄

N개의 수

셋째 줄부터 M개의 줄

i j

조건

1 ≤ N, M ≤ 100,000

---

출력

각 구간에 대해 합을 출력한다.

---

입력 예시

5 3
5 4 3 2 1
1 3
2 4
5 5

출력 예시

12
9
1

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

누적합(prefix sum)

---

기본 아이디어

매번 구간 합을 직접 계산하면

O(N)

이 걸린다.

M번 반복하면

O(N × M)

→ 시간초과

---

해결 방법

누적합 배열을 만들면

구간합 = acc[j] - acc[i-1]

으로 한 번에 계산 가능

---

내가 작성한 코드

나는 입력을 받으면서 누적합을 바로 계산했다.

코드

import java.util.*;

class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] nums = new int[N];
        int sum = 0;

        for(int i = 0; i < N; i++) {
            sum += sc.nextInt();
            nums[i] = sum;
        }

        for(int j = 0; j < M; j++) {

            int start = sc.nextInt();
            int end = sc.nextInt();

            if(end == 1 && start == end) {
                System.out.println(nums[end-1]);
            }

            else if(start != 1) {
                System.out.println(nums[end-1] - nums[start-2]);
            }

            else {
                System.out.println(nums[end-1]);
            }
        }
    }
}

---

강의 코드

강의에서는 누적합 배열을 따로 만들어 더 간단하게 처리했다.

코드

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] arr = new int[N + 1];

        for (int i = 1; i <= N; i++)
            arr[i] = sc.nextInt();

        int[] acc = new int[N + 1];

        for (int i = 1; i <= N; i++)
            acc[i] = acc[i - 1] + arr[i];

        while (M-- > 0) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            System.out.println(acc[j] - acc[i - 1]);
        }
    }
}

---

내 코드 vs 강의 코드 비교

1. 누적합 배열 구조

내 코드

0번부터 시작 (0-index)

nums[i] = sum;

---

강의 코드

1번부터 시작 (1-index)

acc[i] = acc[i-1] + arr[i];

---

핵심 차이

방식	특징
내 코드	0-index 기반
강의 코드	1-index 기반

---

2. 구간 합 계산

내 코드

if(start != 1)
    nums[end-1] - nums[start-2]

→ 조건 분기 필요

---

강의 코드

acc[j] - acc[i - 1]

→ 조건 없이 처리 가능

---

핵심 차이

내 코드 → 조건 분기 필요
강의 코드 → 조건 없이 계산 가능

---

3. 코드 간결성

내 코드

if문 여러 개 필요

---

강의 코드

한 줄로 처리

---

4. 실전에서 어떤 게 더 좋은가

강의 코드 방식이 더 많이 사용된다.

이유

1-index 사용 → 실수 줄어듦
조건문 제거 → 코드 간결

---

핵심 개념

1. 누적합 (Prefix Sum)

acc[i] = acc[i-1] + arr[i]

---

2. 구간 합 공식

i ~ j = acc[j] - acc[i-1]

---

3. 시간 복잡도

• 누적합 생성: O(N)
• 질의 처리: O(M)

전체

O(N + M)

---

정리

이 문제는 대표적인 누적합 문제이다.

내 코드는 누적합을 직접 만들었지만
조건 처리가 많아 코드가 복잡해졌다.

강의 코드는

1-index 누적합

을 사용해서 더 깔끔하게 해결했다.

핵심 차이는 다음과 같다.

내 코드   → 조건 분기 기반 계산
강의 코드 → 공식 기반 계산

즉, 이 문제는

누적합 공식을 제대로 이해하는 것이 핵심

인 문제였다.