백준 11501

백준 11501
일단 이 문제는 최대로 얻을 수 있는 주식의 이익을 구하는 문제이다.
최대 이익을 얻기 위해서는 단순하게 고점보다 낮은 가격일 때, 다 사들여서 고점에 파는 주식 문제이다.

그럼 최고점이 나오기 전까지는 계속 주식을 사고 최고점이 나왔을 때, 주식을 다 털어내면 된다. 근데 이 때 주의해야 할 점이 최고점이 나온 날 이후에도 주식 가격이 계속 보일 수도 있어서 그 다음 최고점을 구해야 한다.

ex) 5
1 2 4 1 3  => 1, 2에 다 사들이고 4에 다 털고, 다시 1에 사들이고 3에 팔아야 한다.

그래서 주식의 가격을 배열 인덱스로 표현을 해서 최고점의 가격이 0이면 다음 고점으로 최고점을 넘기는 식으로 표현을 했다.

ex) 위 와 같은 경우 arr[1]=2 , arr[2]=1 , arr[3] =1 , arr[4] =1 이 된다.

#include<bits/stdc++.h>
using namespace std;
int t;
int arr[10001];
int main() {

ios::sync_with_stdio(0); cin.tie(0);

cin >> t;

while (t--) {
	int n; int st = 0;
	int maxN = 0; // 최댓값 
	vector<int>v;
	long long sum = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		arr[a]++;
		if (maxN < a) maxN = a;
		v.push_back(a);
	}

	for (int i = 0; i < n; i++) {
		
		if (arr[maxN]!=0 &&maxN == v[i]) {
			for (; st <= i; st++) {
				sum += maxN - v[st];
			}
			st = i + 1;
		}
		arr[v[i]]--; // 지나간 주식 가격의 수량을 다 빼줌

		if (arr[maxN] == 0) { // 최고점에 팔고 다음 최고점을 구하기 위함
			while (arr[maxN] == 0) {
				maxN--;
			}
		}

	}
	cout << sum<<'\n';
}

}

처음에 자료형을 int로 잡아서 틀렸다. 최대 가격이 10000 이하에다가 N이 백만개인데, 대략 10000* 백만개 하면 int형을 훨씬 넘는다. 주의해서 풀어야 한다. 시간초과가 왜 안나는지는 잘 모르겠다. 5초라 널널한건가

그냥 뒤에서부터 최대값을 잡고 그 최대값보다 작으면 최대값-v[i]를 하고 sum에 더하면 더 쉽고 깔끔한 풀이가 나온다.. 굳이 최대값을 arr[i]배열로 찾을 필요가 없다

#include<bits/stdc++.h>
using namespace std;
int t;
int main() {

	ios::sync_with_stdio(0); cin.tie(0);

	cin >> t;

	while (t--) {
		int n; 
		int maxN = 0; // 최댓값 
		vector<int>v;
		long long sum = 0;

		cin >> n;

		for (int i = 0; i < n; i++) {
			int a;
			cin >> a;
			v.push_back(a);
		}

		for (int i = n - 1; i >= 0; i--) {
			if (maxN < v[i]) maxN = v[i];
			else sum += maxN - v[i];
		}
		
		cout << sum << '\n';
	}
}