[C++ 삼성 SW D2] 1859. 백만 장자 프로젝트

SW Expert Academy

SW Expert Academy

문제는 다음링크 참조

처음에 vector 사이즈를 int로 했더니 제한시간 초과를 해서 long long 사이즈로 변경해 문제를 풀었다.

 

문제해설

맨 뒤에 값을 MAX로 설정하고 값이 MAX보다 크면 MAX값 갱신 아니면 차를 구해 SUM에 더해주는 방식으로 풀었다.

 

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

using namespace std;


int main(void) {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        vector<long long> arr(n);
        for (int j = 0; j < n; j++)
        {
            cin >> arr[j];
        }
        long long sum = 0;
        long long max_ = arr[n - 1];
        for (int z = n - 2; z >= 0; z--)
        {
            if (arr[z] > max_)
            {
                max_ = arr[z];
            }
            else
            {
                sum += max_ - arr[z];
            }
        }
        cout << "#" << i + 1 << " " << sum << endl;
    }
    return 0;
}