백준11501 - 주식

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

11501번: 주식

생각의 전환이 필요한 문제였다. 현재 주식값보다 제일 비싸지는 미래의 값을 찾아서 가장 이득이 많이 남을때 팔아버리면 되지만 앞에서부터 큰 값을 찾아가는 과정은 너무 시간이 오래걸렸다. 따라서 가장 먼 미래인 맨 뒤에서부터 이득이 가장 커지는 경우를 찾아가면 되었다. 현재 최대 주식 차익을 결정하기 위해서 가장 우선적으로 가장 먼 미래의 값을 찾아 점점 가까운 미래로 접근하면서 가장 이득이 클 때를 찾으면 되기 때문이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int T;
    
    cin >> T;
    while(T--) {
        int N;
        long long int num;
        long long int big = -1;
        long long int sum = 0;
        vector<int> v;
        
        cin >> N;
        while(N--) {
            cin >> num;
            v.push_back(num);
        }
        
        reverse(v.begin(), v.end()); //뒤에서부터 비교하기 위함
        
        for(int i = 0; i < v.size(); i++) {
            if(big < v[i]) {
                big = v[i];
            }
            else {
                sum += big - v[i];
            }
        }
        
        cout << sum << '\n';
        
    }
    return 0;
}