[백준 17203] ∑|ΔEasyMAX|

 

 

문제 : https://www.acmicpc.net/problem/17203

17203번: ∑|ΔEasyMAX|

 

부분 합을 구하는 것은 똑같으나 입력받은 배열 그대로의 부분 합이 아니라 변화량의 합을 구해야한다.

변화량을 따로 배열에 구한 뒤 다시 또 변화량의 부분 합을 구해서 답을 출력한다.

 

// ∑|ΔEasyMAX|
// https://www.acmicpc.net/problem/17203
#include <iostream>
#include <numeric>
#include <cmath>
#include <vector>
using namespace std;

int n, q;
vector<int> a, variation, psum;

int range(int s, int e){
    if(s > e-1) return 0;
    return psum[e-1] - psum[s-1];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> q;
    a.resize(n+1);
    variation.resize(n);
    psum.resize(n);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    for(int i = 2; i <= n; i++){
        variation[i-1] = abs(a[i] - a[i-1]);
    }
    
    partial_sum(variation.begin(), variation.end(), psum.begin());
    
    for(int i = 1; i <= q; i++){
        int s, e;
        cin >> s >> e;
        cout << range(s, e) << '\n';
    }
    
    return 0;
}

 

---

 

부분합 함수

2019/08/07 - [PS/Tip] - [C++/STL] 부분 합 partial_sum( )

[C++/STL] 부분 합 partial_sum( )