[백준] 11501번: 주식

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

11501번: 주식

문제 해결 방법 다 고안해놓고 괜히 10만 개 정도는 배열에 못 넣는 줄 알고 돌아 돌아 접근했다.

알고보니 배열에 넣을 수 있더라...?

 

여기서 주식을 통해 이익을 최대화하는 방법은 주식을 가장 싸게 사서, 가장 비싸게 파는 것이다.

여기서 앞에서부터 주식을 사고, 팔았는데 만약 나중에 더 높은 주식 가격이 나온다면...?

 

곤란하다.

그래서 이런 점을 해소하기 위해 뒤에서부터 높은 주식 가격을 파악해나간다.

이를 통해 예를 들어 가장 높은 주식 가격 다음에 나온 주식들은 그 이후에 존재하는 주식 중 가장 높은 주식 가격일 때 처분한다.

 

이로써 다시 한 번 강조하지만 문제를 어렵게 꼬아서 생각하면 나만 힘들다..

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int T, N;
	cin >> T;
	while(T--) {
		cin >> N;
		long long answer = 0;
		vector<int> stocks(N);
		for(int i = 0;i < N;i++){
			cin >> stocks[i];
		}
		int highest_price = 0;
		for(int i = N - 1;i >= 0;i--) {
			if(stocks[i] > highest_price) {
				highest_price = stocks[i];
			}
			else {
				answer += highest_price - stocks[i];
			}
		}

		cout << answer << '\n';
	}
}