알고리즘 공부

백준 주식

컴퓨터과학 2023. 7. 29. 17:09

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

 

11501번: 주식

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타

www.acmicpc.net

진짜 그리드 알고리즘 거지같네요...

이틀동안 이것만 봄 ㅋㅋ 진짜 또 보면 막상 그렇게 복잡하지도 않네요 ㅎㅎ 시간초과 진짜

그리드 알고리즘의 포인트중 하나가 O(N) 기준을 항상 맞춰야하고 타입을 long long 을 엄청 좋아하네요..ㅎ 

아..ㅋㅋ 진짜 짜증나네여

#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;

struct Point {
	int s, e, t, cnt, power;
	char c;
};

void Prints(vector<vector<int>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void Prints(vector<vector<bool>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<char>>maps, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<vector<char>>>maps, int n, int m, int k) {
	for (int t = 0; t < k; t++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << maps[t][i][j];
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << endl;
}

void Prints(vector<vector<vector<bool>>>maps, int n, int m, int k) {
	for (int t = 0; t < k; t++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << maps[t][i][j];
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(string str, int n) {
	for (int i = 0; i < n; i++) {
		cout << str[i] << ",";
	}
	cout << endl;
}

struct Data {
	unsigned long long index;
	unsigned long long value;
};

bool compares(const Data &a, const Data &b) {
	if (a.value == b.value) {
		return a.index > b.index;
	}
	return a.value > b.value;
}

int main() {
	//1 4 6
	unsigned long long T;
	cin >> T;
	vector<unsigned long long>gCount;
	for (unsigned long long k = 0; k < T; k++) {
		unsigned long long n;
		cin >> n;
		vector<Data>data;
		vector<Data>initdata;
		for (unsigned long long i = 0; i < n; i++) {
			unsigned long long tmp;
			cin >> tmp;
			Data d;
			d.index = i;
			d.value = tmp;

			data.push_back(d);
			initdata.push_back(d);
		}
		
		unsigned long long totalsum = 0;
	
		unsigned long long sum = 0;
		unsigned long long cnt = 0;
		unsigned long long dIndex = 0;
		unsigned long long max = 0;
		for ( long long i = initdata.size()-1; i >=0; i--)
		{ 
			if (initdata[i].value > max) {
				
				//cout <<"cnt" <<cnt << endl;
				//cout <<"sum"<< sum << endl;
				
				totalsum = totalsum + max * cnt - sum;
				//cout << "totalsum" << totalsum << endl;
				
				//cout << totalsum;
				max = initdata[i].value;
				//cout << "max:" << max << endl;
				//cout << endl;
				cnt = 0;
				sum = 0;
			}
			else {
				
				sum=sum+initdata[i].value;
				cnt++;
			}
		}

		if (sum > 0) {
			totalsum = totalsum + max*cnt - sum;

		}

		//cout <<"totalsum:"<< totalsum << endl;
		gCount.push_back(totalsum);
	}
	for (unsigned long long i = 0; i < gCount.size(); i++) {
		cout << gCount[i] << "\n";
	}
	return 0;
}