백준 11659-구간 합 구하기 4(C++)

문제로 바로 가기

-> 백준링크

---

문제 설명

정수로 이루어진 길이 N짜리 배열이 주어진다.
그리고 M개의 쿼리가 들어오는데, 각 쿼리는 인덱스 i부터 j까지의 구간 합을 구하라는 것.

• 1 ≤ N, M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

시간 제한은 1초.
단순히 매 쿼리마다 합을 직접 계산하면 시간초과가 난다.
O(N * M) 시간복잡도라 당연히 터짐.

---

핵심 아이디어

누적합(Prefix Sum) 배열을 만들어두면,
i부터 j까지의 합을 O(1) 시간에 구할 수 있다.

누적합 배열 S를 다음과 같이 만든다:

S[i] = S[i-1] + A[i] (1-based indexing)

그럼 구간 [i, j]의 합은:

S[j] - S[i-1]

딱 한 번 계산한 값들을 재활용하는 방식.
이게 바로 동적 계획법(DP) 방식이고,
구간합 문제의 전형적인 풀이다.

---

실패했던 시도

처음엔 Python에서 accumulate로 매번 구간합 계산해보려 했는데,
M개의 쿼리에 대해 전부 슬라이싱 계산하니까 시간초과 발생.
누적합을 “써먹는 방식”이 아니었기 때문에 의미가 없었다.

---

정답 코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M;
    cin >> N >> M;

    vector<int> nums(N + 1);
    vector<int> prefix(N + 1, 0); // 누적합 배열
    vector<int> answers;

    for (int i = 1; i <= N; i++) {
        cin >> nums[i];
        prefix[i] = prefix[i - 1] + nums[i]; // 누적합 계산
    }

    while (M--) {
        int i, j;
        cin >> i >> j;
        answers.push_back(prefix[j] - prefix[i - 1]);
    }
    
    for(int a:answers){cout<<a<<'\n';}

    return 0;
}

1. 입력받은 배열로 누적합 배열을 만든다.
2. 각 쿼리마다 O(1) 연산으로 정답을 출력한다.

시간복잡도는:

• 누적합 생성: O(N)
• 쿼리 처리: O(1) × M = O(M)
• 전체: O(N + M)

→ 1초 안에 무난하게 통과.

---

마무리

이 문제는 사실상 누적합을 알고 있냐 모르냐가 핵심이다.
구간합을 자주 묻는 문제에서는 거의 필수 전략이니까
다른 유사문제에도 바로 응용 가능하다.

다음부터는 이런 문제 보이면 무조건 누적합부터 생각하고 시작하자.