[Baekjoon] 11501번: 주식

🥅 문제

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

 

🔍 설계

어느 날의 가격보다 이후의 날 가격들 중 가장 높을 때 팔아야 이익을 최대화할 수 있다. 가장 가격이 높은 날에 팔고, 그 날 이후의 날들 중에서 가장 가격이 높은 날 팔고, 이 방식을 반복해야 한다.

 

현재 상황에서 가장 높은 가격을 구하기 위해 우선순위 큐를 활용했는데, 중요한 것은 남아있는 가격들 중 가장 높은 가격에 차익을 보고 판매한 주식 가격들이 있으므로, 인덱스를 함께 담아 제거해야 한다.

---

 

맨 뒤까지 고려했을 때, 주식 가격이 가장 높은 지점에서 팔아야 한다. 순서를 바꿔서 맨 뒤부터 최댓값을 갱신하면서 차이를 빼주면 간단하게 해결할 수 있다.

 

👊 풀이

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

int t, n;
vector<int> prices(1000000);

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		priority_queue<pair<int, int>> pq;
		long long result = 0;
		for (int j = 0; j < n; j++) {
			cin >> prices[j];
			pq.push({ prices[j], j });
		}

		int max_value;
		for (int j = 0; j < n; j++) {
			while (pq.top().second < j) {
				pq.pop();
			}
			max_value = pq.top().first;
			if (max_value > prices[j]) {
				result += (max_value - prices[j]);
			}
		}
		cout << result << "\n";
	}

	return 0;
}

---

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

int t, n;
vector<int> stock(1000000);

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> t;

	for (int u = 1; u <= t; u++) {
		long long result = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> stock[i];
		}

		int max_value = stock[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			max_value = max(max_value, stock[i]);
			result += max_value - stock[i];
		}

		cout << result << "\n";
	}
	return 0;
}