백준 11441번 [합 구하기](C++) -yes6686- 티스토리

백준 문제 풀이: 11441

---

문제 링크: https://www.acmicpc.net/problem/11441

문제 설명:

정수 배열이 주어질 때, 특정 구간 합을 빠르게 구하는 문제입니다. 주어진 n개의 정수에 대해, m개의 질의로 구간 합을 요청합니다. 구간 합은 arr[i] + arr[i+1] + ... + arr[j]로 정의됩니다.

---

문제 해결 코드

// 합 구하기 문제의 최적화된 코드
#include <iostream>
using namespace std;

int prefixSum[100001]; // 누적 합 배열

int main() {
    ios::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(NULL);

    int n;
    cin >> n;

    // 배열 입력 및 누적 합 계산
    for (int i = 1; i <= n; i++) {
        int num;
        cin >> num;
        prefixSum[i] = prefixSum[i - 1] + num;
    }

    int m; // 질의 개수
    cin >> m;
    while (m--) {
        int i, j;
        cin >> i >> j;
        // 구간 합 출력
        cout << prefixSum[j] - prefixSum[i - 1] << '\n';
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 구간 합을 빠르게 계산하기 위해 누적 합(Prefix Sum) 배열을 사용합니다. 누적 합을 이용하면 구간 합을 O(1)에 계산할 수 있습니다.
• 구현 세부사항:
• prefixSum[i]: 배열의 1번부터 i번까지의 합을 저장합니다.
• prefixSum[j] - prefixSum[i-1]: 구간 [i, j]의 합을 빠르게 계산합니다.
• 배열은 1-based index로 접근하며, 입력 범위에 따라 배열 크기를 충분히 확보합니다.
• 시간 복잡도 분석:
• 누적 합 계산: O(n) (입력 배열 크기만큼 한 번의 순회)
• 질의 처리: 각 질의에 대해 O(1) (구간 합 계산)
• 전체 시간 복잡도: O(n + m), 여기서 n은 배열 크기, m은 질의 개수입니다.

---

결과

최적화된 누적 합 알고리즘으로 구간 합을 효율적으로 계산할 수 있습니다. 입력 크기가 커질수록 시간 복잡도 O(n + m)의 장점이 두드러집니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!