Lee's Programming Practice

문제

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

풀이

구현문제이긴 하나, 자료형의 범위와 시간복잡도를 고려해야하는 문제다.

MAX_ELEMENT 또한 결국 시간복잡도를 많이 먹는 함수라 그냥 반복문 한번으로 돌릴 방법을 고민하면 된다.

소스 코드

#include<iostream>

using namespace std;

int arr[1000001], N;

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin>>T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
		int max = 0;
		long long sum = 0;

		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> arr[i];
		}
		
		max = arr[N];

		for (int i = N - 1; i > 0; i--) {
			if (max < arr[i]) {
				max = arr[i];
			}
			else {
				sum += max - arr[i];
			}
		}

		cout << "#" << test_case << " " << sum << '\n';
	}
	return 0;
}