1859. 백만 장자 프로젝트

1859. 백만 장자 프로젝트

문제출처: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

풀이 방법

가장 어려웠던 문제였다 첨엔 DFS를 이용하여 풀어서 시간초과가 떴다. 하지만 뒤에서부터 하나씩 잡아 팔았을때 가장 비싼 경우를 찾는다.

<코드>

#include <iostream>
#include <cstring>
using namespace std;

long long int* dataArray;
long long int answer = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int test_case;
	int T;

	cin >> T; 

	for (test_case = 1; test_case <= T; ++test_case)
	{
		int n;
		std::cin >> n;

		dataArray = new long long int[n];
		answer = 0;
		for (long long int i = 0; i < n; i++)
			std::cin >> dataArray[i];

		int checker = n - 1;
		for (long long int i = n - 2; i >= 0; i--)
		{
			if (dataArray[checker] > dataArray[i])
				answer += (dataArray[checker] - dataArray[i]);
			else
				checker = i;
		}

		delete[] dataArray;

		std::cout << "#" << test_case << " " << answer << "\n";
	}

	return 0;
}