[ 백준 / C++ ] 11501 : 주식

[ 문제 ]

 

11501번: 주식

 

[ 접근방법 ]

 

입력을 내림차순 정렬한 후 순회하면서, 현재 처리중인 인덱스보다 순회중인 인덱스가 큰 경우 차이를 계산한다.

 

이 과정에서 구간합을 빠르게 구하기 위해 sum 배열을 미리 만들었다.

 

시간복잡도는 t * O(n log n) 이다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

bool cmp(pair<ll, int> x, pair<ll, int> y){
    if(x.first != y.first)return x.first > y.first;
    return x.second > y.second;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while(t--){
        int n;
        cin >> n;

        vector<pair<ll, int>> vec(n + 1);
        vector<ll> sum(n + 1, 0);

        for(int i = 1; i <= n; i++){
            cin >> vec[i].first;
            vec[i].second = i;
            sum[i] = sum[i - 1] + vec[i].first;
        }

        sort(vec.begin() + 1, vec.end(), cmp);

        int idx = 1;
        ll ans = 0;

        for(int i = 1; i <= n; i++){
            if(idx <= vec[i].second){
                ans += (vec[i].second - idx) * vec[i].first - (sum[vec[i].second - 1] - sum[idx - 1]);
                idx = vec[i].second + 1;
            }
        }

        cout << ans << "\n";
    }

    return 0;
}