알고리즘 공부
백준 주식
컴퓨터과학
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;
}