[SWEA] 1859. 백만 장자 프로젝트

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

SW Expert Academy

나는 답을 구하는 과정을 너무 복잡하게 생각했더니 감이 안잡혀서 코드를 찾아봤더니 단순한 알고리즘이었다.

매매가 벡터의 뒤에서부터 루프를 도는데 초기에는 마지막 값을 max에 넣고 시작하고, 그 다음부터 max 값보다 작으면 산다고 가정하고 이익을 결과 값에 더해주고, max 값과 같거나 크면 max 값을 해당 값으로 바꿔주면 된다.

주의할 점은 숫자가 큰 테스트 케이스의 경우에 int형의 범위를 넘어가기 때문에 결과 값의 자료형을 long long으로 설정해주어야 한다는 점이다.

#include <iostream>
#include <ios>
#include <vector>
using namespace std;

int T, N;
vector<int> prices;
long long getResult();

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> T;
	for (int testCase = 1; testCase <= T; testCase++) {
		prices.clear();
		cin >> N;
		for (int i = 0; i < N; i++) {
			int temp; cin >> temp;
			prices.push_back(temp);
		}
		cout << '#' << testCase << ' ' << getResult() << "\n";
	}
	return 0;
}

long long getResult() {
	int max = prices[N - 1];
	long long profit = 0;
	for (int i = N - 2; i >= 0; i--) {
		if (prices[i] < max) {
			profit += max - prices[i];
		}
		else {
			max = prices[i];
		}
	}
	return profit;
}