[백준][그리디] 11501 주식 c++ 구현

목차

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

11501번: 주식

문제

 

문제 풀이 시 주의해야 할점

이중반복문을 돌리게 되면 시간 복잡도가 O(N^2)이 나와 시간초과로 틀리게 된다.

따라서 전처리를 통해 자기보다 큰 것이 없는지 있는지 정해주어 풀면시간복잡도가 O(N)으로 풀리게 도힌다.

 

 

문제 풀이

오늘보다 뒷날에 주가가 더 큰 것이 있다. 

• 매수한다.

오늘보다 뒷날에 더 큰 것이 없다. 

• 주식이 있다면 판다.
• 주식이 없다면 나둔다.

이런식의 최적 부분구조로 구현하면 됩니다.

 

 

코드 구현

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int>> arr;  // 주가와 뒷날에 더 큰 주가가 있는지 설정을 위한 pair
long long int Benefit() {
	long long int i, j, nums=0, buysum =0, benefit=0, check=0;
	for (i = 0; i < arr.size(); i++) {
		check = 0;
		int k = 0;
	
		if (arr[i].second == 1) {   //뒷날에 더큰 주가가 있으므로 매수해 줍니다.
			nums++;
			buysum += arr[i].first;
		}
		else {   // 뒷날에 더 큰 주가가 없을 경우
			if (nums == 0) {   //보유 주식이 없으므로 나둡니다.
				;
			}
			else {  //보유 주식이 있으므로 팔아줍니다.
				benefit += arr[i].first * nums - buysum;
				nums = 0;
				buysum = 0;
			}
		}
	}
	return benefit;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int day, i, j, nums, price;

	cin >> day;
	for (i = 0; i < day; i++) {
		cin >> nums;
		arr.clear();

		for (j = 0; j < nums; j++) {
			cin >> price;
			arr.push_back(make_pair(price, 0));   //주가를 설정하고 기본적으로 0으로 초기화합니다.
		}

		//전처리 과정
		int max = arr[nums-1].first;  //max로 첫 주가 값을 설정한다.
		for (j = nums-1; j >=0 ; j--) {
			
			if (arr[j].first >= max) {   // max보다 크면 주가를 현재 값으로 만듭니다.
				max = arr[j].first;
			}
			else {   //max보다 작으면 뒷날에 더 큰 주가가 있음을 표시합니다.
				arr[j].second = 1;
			}
		}

		cout << Benefit()<<"\n";
	}

}