[BOJ/C++] 11501 주식 : Greedy

문제

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

풀이

이론 상으로는 최댓값일 때까지 산 다음 팔고, 다시 나머지 중 최댓값 일 때까지 산다음 팔고 해야 함!
처음에 이렇게 풀었는데 n이 백만까지라 계속해서 최댓값을 찾는 게 엄청 오래 걸리고 복잡함

최댓값 찾아도 뒤에 나오는 주식들은 다시 처음부터 사고 팔고를 해야 함
➡️ 뒤에 나오는 최댓값에 따라 최대이익이 결정됨

⭐뒤에서부터 체크⭐
뒤에서부터 탐색할 경우, O(n)에 풀이 가능

• 값이 커지는 시점 : 최댓값 갱신
• 값이 작아지는 시점 : 최댓값 - v[i]를 최대이익에 합해주기

ex)

⚠️범위 10억(1,000,000,000) 넘어가면 long long형으로 선언하기

코드

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int T;

	cin >> T;
	while (T--) {
		int n;
		vector<int> v;
		int max = 0;
		long long ans = 0;

		cin >> n;
		for (int i = 0; i < n; i++) {
			int tmp;

			cin >> tmp;
			v.push_back(tmp);
		}

		max = v.back();
		for (int i = n-2; i >= 0; i--) {
			if (v[i] >= max) {
				max = v[i];
			}
			else {
				ans += max - v[i];
			}
		}

		cout << ans << '\n';
	}

	return 0;
}