[BaekJoon 11659][⚪3] 구간 합 구하기 4

❓ 문제

백준 11659 - “구간 합 구하기 4”

🎯 난이도

Silver ⚪3

🧠 풀이

1. 내 풀이 (누적 합)

- 알고리즘

• Prefix Sum

- 설명

누적 합 알고리즘을 사용한 풀이이다.

일반적으로 1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000의 조건에서 입력 받는 특정 구간 내의 모든 값들을 순회하며 합을 구하는 방식으로 하게 되면, 너무 비효율적이다. 따라서 미리 'i'번째까지의 합들을 모두 구해서 저장해 놓은 뒤, 그 합들끼리의 뺄셈 계산을 하는 방식의 '누적합' 방식으로 하면, 훨씬 빠르고 효율적이게 결과를 구하는 것이 가능하다.

참고로 누적합의 값이 int 범위를 벗어날 가능성도 있으니 꼭 long long 자료형을 쓰는 것에 주의하도록 하자.

입력을 받으며 미리 합들을 계산하고, 반복문을 돌며 그 결과값을 출력하기만 하므로 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{}, iM{};
    cin >> iN >> iM;

    // 누적합 계산 및 저장
    vector<long long> vecSum(iN + 1);
    for(int i = 1; i <= iN; ++i)
    {
        int iInput{};
        cin >> iInput;

        // 이전 누적합 + iInput 값 저장
        vecSum[i] = vecSum[i - 1] + iInput;
    }

    while(iM--)
    {
        int iI{}, iJ{};
        cin >> iI >> iJ;

        // 특정 범위의 합을 바로 출력
        cout << vecSum[iJ] - vecSum[iI - 1] << '\n';
    }

    return 0;
}

---

💭 후기

일반적으로 이런 문제처럼 특정 구간 내의 모든 합들을 구하라 식의 문제는 누적합으로 쉽게 풀 수 있다. 그 외에도 누적합은 보통 메인 알고리즘보다는 다른 알고리즘과 같이 사용되는 서브 알고리즘으로도 자주 활용되니 잘 익혀두자.

🔗 참고자료

• 누적 합