[BOJ] 11659 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

누적 합

 

---------------------------------------------------풀이----------------------------------------------------

 

문제는 1~N까지로 인덱스가 주어졌지만, 0~N-1까지로 풀었다. (1~N으로 했다면 더 깔끔한 코드가 됐을 것이다.)

 

우선, 누적합을 저장할 sum[] 배열을 정의한다. sum[i]는 0~i번째 까지의 합을 의미한다.

a에서 b번째 까지의 합을 구하려면,

(0~b번째 까지의 합) - (0~a-1번째 까지의 합) 을 계산하면 된다.

다시 말해, sum[b] - sum[a-1]이 정답이다.

 

이때, 0~N-1로 바꿨기 때문에 a가 0일 경우 sum[a-1]은 sum[-1]을 참조하게 되어 오류가 발생할 수 있다.

따라서, 예외 처리를 따로 해줬는데,

문제에 제시된대로 1~N까지로 했다면 sum[0] = 0으로 저장해 두면 되므로

a가 1이더라도 sum[a-1]은 sum[0] = 0이므로 조금 더 깔끔한 코드를 작성할 수 있다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <deque>

using namespace std;

// [0,i]까지의 합
int sum[100'001] = {0, };

// 구간 [a,b]의 합을 구해라
int main(void){
    FASTIO;
    int N, M;
    cin >> N >> M;
    int tmp, total = 0;
    for(int i = 0; i < N; i++){
        cin >> tmp;
        total += tmp;
        sum[i] = total;
    }
    int a, b;
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        a--; b--;   // 실제 입력은 1~ 로 들어오기 때문에, 저장된 0~ 로 변경
        // sum[b]-sum[a-1]
        if(a == 0){
            cout << sum[b] << "\n";
        }
        else{
            cout << sum[b]-sum[a-1] << "\n";
        }
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

보자마자 누적합이 떠올랐던 문제.