[SWEA] C++ 7829. 보물왕 태혁(D2)

문제 바로가기

접근방법

1. 가장 비싼 가격을 찾아 그 날 물건을 팔아야 한다.
2. 그런데 가장 비쌀 때 물건을 팔았는데 그 후에도 거래가 이루어진다면 거기서 가장 비싼 가격을 찾아서 팔면 된다.
   ex) 1 1 3 1 2가 있다고 치자.
   3일 때가 가장 비싸 1, 1을 사서 팔았다. 그런데 2일이나 더 거래를 해야 한다. 그러면 남은 1 2중 가장 비싼 가격인 2인 날에 1을 팔아야 한다.
3. 벡터의 max값을 구하는 코드를 사용하면 쉽게 구할 수 있다.

슈도코드

if max != [i]
 sum += [i]
 pop
 cnt++
else
 max * cnt - sum
 pop
 find new max

풀이

#include <cstdio>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

int T, test_case, N, cnt, i;
long long x, maxNum, sum, answer;
vector<int> v;

void input_price() {
	for (int i = 0; i < N; i++) {
		cin >> x;
		v.push_back(x);
	}
}

void hoarding() {
	while (!v.empty()) {
		if (maxNum != v[i]) {
			sum += v[i];
			cnt++;
			i++;
		}
		else {
			answer += maxNum * cnt - sum;
			v.erase(v.begin(), v.begin() + i + 1);
			sum = 0, cnt = 0, i = 0;
			if (!v.empty())
				maxNum = *max_element(v.begin(), v.end());
		}
	}
}

int main() {
	cin >> T;

	for (test_case = 1; test_case <= T; test_case++) {
		cin >> N;

		input_price(); // 가격 입력 받기

		maxNum = *max_element(v.begin(), v.end()); // 최대값 찾아놓기
		sum = 0, cnt = 0, answer = 0, i = 0; // 초기화

		hoarding(); // 사재기
		
		cout << "#" << test_case << " " << answer << "\n";
		v.clear();
	}
	return 0;
}