[백준] 11659번 구간 합 구하기 4 C++풀이

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

---

알고리즘 분류

• 누적 합

---

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

---

입력 설명

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

---

출력 설명

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

---

예제 입력

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

---

예제 출력

12
9
1

 

 

---

제한

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

---

아이디어

1. n칸 배열에 입력받은 수를 모두 저장하고 매번 i ~ j까지 더한 후 출력한다. -> 최악의 경우 1 ~10만까지의 합을 10만번 반복 계산 해야하므로 시간 초과 발생

 

2. 2차원 배열을 사용해서 i ~ j 까지의 누적합을 DP[i][j]에 기록하고 기록된 값이 있다면 해당 값을 출력하고 없다면 DP[i][j] = DP[i][j-1] + DP[j][j]를 재귀적으로 반복하여 최종적으로 DP[i][j]를 출력한다. -> 1 ~ 10만까지의 합은 50005000이다. 이렇게 큰 수를 배열에 전부 넣으려면 메모리가 부족하므로 메모리 부족으로 실패

 

3. i ~ j 까지의 누적 합은 (1 ~ i 까지의 누적 합) - (1 ~ j-1까지의 누적 합)을 이용한다.

---

알고리즘

숫자를 입력받을 때부터 누적합을 계산하여 저장한다.

DP[i] = DP[i-1] + input;

a ~ b의 누적 합은 DP[b] - DP[a-1]이므로 해당 값을 출력한다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int n, m, a, b, temp;
    cin>>n>>m;
    vector<int> DP(n+1);
    DP[0] = 0;
    for(int i=1; i<=n; i++)
        {
            cin>>temp;
            DP[i] = DP[i-1] + temp;
        }
    for(int i=1; i<=m; i++)
        {
            cin>>a>>b;
            cout<<DP[b]-DP[a-1]<<"\n";
        }
    return 0;
}

---

후기

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

매번 누적 합을 구하는 방식은 당연히 틀릴 거라고 예상했고

DP를 사용하는 방식은 맞을 거라고 예상했는데

저장되는 숫자가 커서 메모리 초과가 났다.

이후 누적 합을 사용해야 한다는 힌트를 보고 문제를 풀 수 있었다. 

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!