SW Export Academy 1859 백만 장자 프로젝트

원재가 어떤 물건을 조건 하에 사재기를 하려고 하는데 조건은 다음과 같다.

1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.

2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.

 

예를들어 5일동안 물건의 매매가를 6 9 1 1 3 으로 알고있을때 조건을 만족했을때 최대로 얻을 수 있는 이득은 6을 사고 9에 팔고 1을 사고3에 팔아서 총 7만큼 최대 이익을 챙길 수 있다.

 

처음 문제를 보았을때 최대 이익을 얻기 위해서 우선순위 큐를 생각하였다. 하지만 이를 이용하면 인덱스의 순서가 바뀌게 되어 우선순위 큐를 관리해주어야 한다.

 

우선순위 큐를 이용하여 구현한 방식이다.

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

void solution(int t)
{
	int n;
	cin >> n;
	priority_queue < pair<int, int>, vector < pair<int, int>>, less<pair<int, int>>> pq;
	vector<int> v;
	for(int i = 1; i <= n; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
		pq.push({ num,i });
	}


	long long total = 0;
	for(int i = 0; i < v.size(); i++)
	{
    	//while을 통해 우선순위 큐 top에 있는 인덱스가 현재 인덱스보다 작거나 같으면 큐에서 빼준다.
		while(!pq.empty() && i + 1 >= pq.top().second)
		{
			pq.pop();
		}

		if(pq.empty())
		{
			break;
		}
		pair<int, int> top = pq.top();

		if(v[i] < top.first)
		{
			total += (top.first - v[i]);
		}
	}
	cout << "#" + to_string(t) + " " << total;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
		solution(test_case);
		cout << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

위의 while을 적용하지 않으면 뒤에 인덱스가 앞에 인덱스와 비교하는 경우가 발생하여 답을 구할수 없다. 또한 이 방법을 사용하면 while을 수행하여 우선순위 큐를 삭제 해주어야 하기 때문에 삭제하는데 O(logN)의 시간 복잡도가 걸린다. 따라서 전체 시간 복잡도는 O(n^2logN)이다. 

 

조금더 간단한 풀이로는 뒤에서부터 탐색하여 maxProfit을 업데이트 하면서 합계를 구하는 방법이다. 이 방법은 O(n)의 시간 복잡도 안에 최대 이익을 찾을수 있다.

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

void solution(int t)
{
	int n;
	cin >> n;
	vector<int> v;
	for(int i = 1; i <= n; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
	}


	int maxProfit = 0;
	long long total = 0;
	for(int i = v.size()-1; i >= 0; i--)
	{
		if(v[i] > maxProfit)
		{
			maxProfit = v[i];
		}
		else
		{
			total += maxProfit - v[i];
		}
	}
	cout << "#" + to_string(t) + " " << total;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
		solution(test_case);
		cout << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 실행 시간을 확인해 보면 약 7배 정도 차이가 나는것을 확인 할 수 있다.