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

백준 문제 풀이: 11659 [구간 합 구하기 4]

---

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

문제 설명:

주어진 수열에서 특정 구간의 합을 빠르게 계산하는 문제입니다. 수열의 합을 효율적으로 구하기 위해 누적 합을 활용합니다.

입력:

• 첫 줄에 수열의 크기 n과 합을 구해야 하는 횟수 m이 주어집니다. (1 ≤ n, m ≤ 100,000)
• 둘째 줄에는 n개의 정수가 주어집니다.
• 다음 m개의 줄에는 합을 구해야 하는 구간 a와 b가 주어집니다. (1 ≤ a ≤ b ≤ n)

출력:

• m개의 줄에 각 구간의 합을 출력합니다.

예시:

입력:
5 3
5 4 3 2 1
1 3
2 4
5 5

출력:
12
9
1

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[100001]; // 입력된 수열
int dp[100001]; // 누적 합 배열

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i]; // 수열 입력
        dp[i] = dp[i - 1] + arr[i]; // 누적 합 계산
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; // 구간 입력
        cout << dp[b] - dp[a - 1] << '\n'; // 구간 합 출력
    }

    return 0;
}

---

코드 설명

이 코드는 누적 합(Prefix Sum)을 사용하여 주어진 구간의 합을 효율적으로 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 누적 합을 사용하면 각 구간의 합을 O(1) 시간에 계산할 수 있습니다.
  • 구간 합은 dp[b] - dp[a-1]로 계산됩니다.
• 구현 세부사항:
  • dp[i]: 1번부터 i번까지의 합을 저장하는 배열입니다.
  • dp[i] = dp[i - 1] + arr[i]: 누적 합 배열을 채우는 과정입니다.
  • 구간 합 계산 시 a-1 인덱스를 조정하여 범위를 포함하도록 처리합니다.
• 시간 복잡도 분석:
  • 누적 합 계산: O(n)
  • 구간 합 계산: O(m)
  • 전체 시간 복잡도: O(n + m)

---

결과

코드는 주어진 입력에 대해 누적 합 배열을 계산하고, 이를 활용하여 각 구간의 합을 빠르게 출력합니다. O(n + m)의 효율적인 알고리즘으로 대량의 데이터도 빠르게 처리할 수 있습니다.

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