주식 C++ - 백준 11501

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

이 문제는 뒤에서부터 탐색하는 방법이 잘 떠오르지 않아,

많이 헤멘 그리디 문제이다.

$i$번째 항은 $i+1$항부터 $n$번째 항까지의 최댓값에 팔아야 이득이다.

따라서 뒤에서 부터 최댓값을 갱신하고, 그 최댓값보다 작으면 파는,

알고리즘을 작성해주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int t;

void solve(){
    int n;
    long long ans=0;
    vector<int> v;
    cin >> n; for(int i=0;i<n;i++){int a;cin >> a;v.push_back(a);}
    int maxi=v.back();
    for(int i=v.size()-2;i>-1;i--){
        if(v[i]>maxi) maxi=v[i];
        else if(v[i]<maxi) ans+=maxi-v[i];
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> t; while(t--) solve();
}