SW Expert Academy - 1859. 백만 장자 프로젝트

문제링크

• 백만 장자 프로젝트

문제설명

• 원재는 연속된 N일 동안의 물건의 매매가를 알고 있다.
• 하루에 구매할 수 있는 물건의 양은 1이다.
• 하루에 판매할 수 있는 물건의 양은 제한이 없다.
• 최대 이익을 계산하라

문제접근

• 우선순위 큐 자료구조를 활용하여 pair<매매가, Day>` 자료형으로 이루어진 최대힙을 만든다.
• 현재 담긴 우선순위 큐에서 원소(매매가, 날짜)를 추출한다.
• 현재 날짜(curDay) < 매매날짜 라면 물건을 계속 산다.
• 현재 날짜(curDay) == 매매날짜 라면 물건을 모두 판다.
• 현재 날짜(curDay) > 매매날짜 라면 물건을 사도 이익을 보지 못하기 때문에 물건을 사지 않는다.
• 위 과정을 큐 버퍼가 비워질 때까지 반복한다.

구현

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

int main(int argc, char** argv)
{
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		long long N;
		cin >> N;
		priority_queue<pair<long long, long long>> pq;
		vector<long long> priceTable;
		long long val;
		for (long long day = 0; day < N; day++) {
			cin >> val;
			pq.push(make_pair(val, day));
			priceTable.push_back(val);
		}
		
		long long curDay = 0, count = 0, price = 0;
		long long ans = 0;
		pair<long long, long long> sellInfo;
		while (!pq.empty()) {
			sellInfo = pq.top();
			long long sellPrice = sellInfo.first;
			long long sellDay = sellInfo.second;
			if (sellDay < curDay) {
				pq.pop();
				continue;
			}

			if (sellDay > curDay) {
				price += priceTable[curDay++];
				count++;
			}
			else if (sellDay == curDay++) {
				ans += (sellPrice * count - price);
				price = 0;
				count = 0;
			}
		}
		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}