[C++/SWEA] 1859. 백만 장자 프로젝트 (D2)

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=CCPP&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

 

아마 그리디? 문제인 것 같다

배열을 역순으로 탐색하면서 max값을 갱신하고, 그보다 작은 값들은 빼주면 된다 (판매 후 차익)

 

나의 풀이

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

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int test_case;
	int T;
	int n;
	
	//freopen("input.txt", "r", stdin);
	
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		vector<long long> v;
		long long num = 0;
		long long answer = 0;
		int maxprice = 0;
		cin >> n;
		for (int i = 0; i < n; ++i){
			cin >> num;
			v.push_back(num);
		}
		maxprice = v[n - 1];
		for (int i = n - 2; i >= 0; --i)
		{
			if(maxprice > v[i]){
				answer += (maxprice - v[i]);
			}
			else{
				maxprice = v[i];
			}
		}
		cout << "#" << test_case << " " << answer << "\n";
	}
	return 0;
}