문제 출처

1. 문제설명

• 주식의 가격이 주어진다.
  • 각 가격은 날짜별 가격이다.
  • 예를들어, [1, 2]라면 첫째날에 1, 둘째날에 2이므로,
  • 첫째날에 사서 둘째날에 팔면 이득이 1이 된다.

2. 알고리즘 설계

• 뒤에서부터 탐색 시작
• 탐색을 하다가 큰 값을 만나면 max_value 갱신
• max_value값과 현재 인덱스의 값을 빼주면 순 이익이 된다.

3. 로직

• 예제분석

  5
  1 1 3 1 2
  
  1. 마지막 index의 값 2부터 탐색 시작
  2. max_value는 2로 설정된다.
  3. 현재 index의 값 2와 max_value값 2의 차이를 더한다.
  4. 1을 만났지만, 2가 더 큰 값이므로 max_value는 갱신되지 않는다.
  5. 2와 1의 차이를 더한다.
  6. 상기 과정 반복
  

4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

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

	int tc; cin >> tc;
	while (tc--) {
		int n; cin >> n;
		vector<int> v(n);
		for (int i = 0; i < n; i++)
			cin >> v[i];

		int cmp = -1;
		long ans = 0;
		for (int i = n - 1; i >= 0; i--) {
			cmp = max(cmp, v[i]);
			ans += cmp - v[i];
		}

		cout << ans << '\n';
	}
	return 0;
}

5. 소감

• 처음에 앞에서부터 접근하는 방식으로 구현
• 뒤에서부터 접근하는 방식으로 변경 후 구현이 매우 수월해짐.