C++ SWEA 1859. 백만 장자 프로젝트

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

SW Expert Academy

풀이

아~ 고민 잠깐하다가 댓글보는 바람에,, 맨 뒤부터 해야한다는 것을 스포당해버렸다,,, 다른 방법을 찾아보려해도 머릿속에 박혀서 그냥 맨 뒤부터 접근해봤숩니다 .. 

 

맨 마지막 값을 최댓값으로 지정한 후에 앞으로 한 칸씩 가면서

만약 최댓값보다 큰 경우 -> 최댓값 변경

만약 최댓값보다 작은 경우 -> 최댓값  - 매매가 를 더해준다.

 

이렇게 하면 최댓값이 항상 뒤에 있기에 이익을 많이 볼 수 있다.

---

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

int arr[1000001] = { 0, };
int main() {
	int test_case;
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) { //초기화
			int tmp; cin >> tmp;
			arr[j] = tmp;
		}
		long long ans = 0; // 정답
		int max_num = arr[num - 1]; 

		for (int i = num - 2; i >= 0; i--) { 
			if (arr[i] < max_num) {  // 최댓값과 i번째 날 값 빼기
				ans += max_num - arr[i];
			}
			else { // 최댓값 변경
				max_num = arr[i];
			}
		}
		cout << "#" << i + 1 << " " << ans << endl;
		memset(arr, 0, sizeof(arr));
	}

	return 0;
}