APS/SWEA

1859. 백만 장자 프로젝트 C++

문래동까마귀 2021. 11. 7. 16:16

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

#include <iostream>
#include <vector>

using namespace std;

vector<long long> arr;
int n;
int cnt = 0;
long long sum = 0;

long long run() {
	int s = arr.size();
	int tmp = arr[s - 1];

	for (int i = s-2; i >= 0; i--) {
		if (tmp <= arr[i]) {
			sum += cnt * tmp;
			cnt = 0;
			tmp = arr[i];
			continue;
		}
		sum -= arr[i];
		cnt++;
		if (i == 0) sum += cnt * tmp;
	}

	return sum;
	
}

int main() {

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

		cin >> n;

		arr.clear();
		for (int x = 0; x < n; x++) {
			int num;
			cin >> num;
			arr.push_back(num);
		}

		sum = 0;
		cnt = 0;
		long long result = run();

		cout << "#" << i + 1 << " " << result << endl;
	}

	return 0;
}