[백준 11501] 주식

백준 11501번 : 주식

www.acmicpc.net/problem/11501

11501번: 주식

 

---

 

/* 문제 설명 */

매일, 세가지 행동 중 하나를 한다.

1. 주식을 하나 산다.

2. 원하는 만큼 가지고 있는 주식을 판다.

3. 아무것도 안한다.

이 때, 최대 이익이 어떻게 되는지 구하시오.

 

/* 해결 방안 */

주가가 낮을 때는 주식을 사야되고, 높을 때는 팔아야 된다.

따라서 최고점일 때 최대한 많이 팔 수 있도록, 최고점보다 낮은 주가를 만날 경우에는 무조건 산다.

→ 그리디

 

참고로, 여기서 최고점은 자신의 오른쪽에 있는 값들 중 가장 큰 값을 의미한다.

 

주가	1	3	5	3	4	2	1
최고점	5	5	5	4	4	2	1

 

따라서 오른쪽에서 왼쪽 방향으로 탐색하여 배열의 각 위치에서의 최고점을 구해준다.

 

/* 구현 과정 */

1. 오른쪽에서 왼쪽 방향으로 탐색을하며, 배열의 각 위치에서의 최고점을 구해준다.

2. 'ans += 최고점-현재 주가'를 해주며 답을 구한다.

 

/* 소스 코드 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll tc, n;
vector<int>v;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n;
		vector<int> arr;
		arr.resize(n + 1);
		for (int i = 1; i <= n; i++) cin >> arr[i];

        ll ans = 0;
		int maxx = arr[n];
		for (int i = n - 1; i >= 1; i--)
		{
			if (maxx <= arr[i]) maxx = arr[i];
			else ans += maxx - arr[i];
		}

		cout << ans << "\n";
		arr.clear();
	}
}

/* 부러운 점 */

나도 주가를 미리 알고 싶다..

 

 

---