[백준 11441번] 합 구하기 (C++)

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

11441번: 합 구하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[100001];
int arr_sum[100001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;

    int sum =0;
    for(int i=1; i<=N; i++)
    {
        cin >> arr[i];
        sum += arr[i]; //누적합구하기
        arr_sum[i] = sum; //각 구간별 누적합 저장
    }

    int M, section1, section2;
    cin >> M;

    for(int i=0; i<M; i++)
    {
        cin >> section1 >> section2;
        cout << arr_sum[section2] - arr_sum[section1-1] << "\n"; //구간별 합 출력
    }
    
    return 0;
}

누적합 문제이다.

오늘까지 예비군 때문에 쉬운 문제 위주로 풀었고, 그 중에 누적합이 약해서 월요일 부터 오늘까지 누적합 문제만 풀었다.

 

이번 누적합 문제는 구간 별 합을 이중 for문으로 구하면 시간초과가 발생하므로 다른 방법으로 풀어야 한다.

처음에 수를 입력받을 때 누적합을 갱신시켜나가고 갱신시킬 때 마다 누적합 전용 배열에 값을 저장해 나간다.

 

이후에 구간을 입력받을 때 이를 이용해서 풀어주면 된다.

ex) 
idx : 1 2 3 4 5
value : 10 20 30 40 50
sum : 10 30 60 100 150
section : 2 4

4번 누적합 (1 ~ 4) : 100
앞의 구역은 2이므로 앞에 부분인 ~1 까지의 합은 필요없음 (2 ~ 4)
-> arr[4] - arr[2-1] 출력