1859. 백만장자 프로젝트

SW Expert Academy

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

swexpertacademy.com

링크

난이도 D2 문제 중 정답률이 가장 낮은 문제다.

접근 방식의 전환이 필요한 문제인듯 하다.

앞에서 뒤로 탐색을 하는 것이 아니라 뒤에서 앞으로 탐색을 하면서 값을 갱신해야한다.

#include <iostream>
#include <string.h>
#define ll long long
using namespace std;
int arr[1000001], tmp[1000001];
int N;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		for (int i = 0; i < N; i++)
			cin >> arr[i];
		ll benefit = 0, max_ = 0;
		for (int i = N - 1; i >= 0; i--) {
			if (max_ <= arr[i]) max_ = arr[i];
			else 
				benefit += max_ - arr[i];
		}
		cout << '#' << tc << ' ' << benefit << '\n';
		memcpy(arr, tmp, sizeof(arr));
	}
	return 0;
}