SWEA 1859 백만 장자 프로젝트

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

SW Expert Academy

 

---

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.

다만 당국의 감시가 심해 한 번에 많은 양을 사재기할 수 없다.

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

    1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
    2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
    3. 판매는 얼마든지 할 수 있다.

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

 

---

문제를 딱 보자마자 '아 이건 그리디다' 하고 생각해서 최대한 부분적인 문제를 해결하려고 접근했다.

 

• 뒷 원소부터 접근해 더 큰 값이 나올때까지 그 차를 결괏값에 더해준다
• 더 큰 원소를 찾았다면 그 큰 값으로 갱신
• 모든 원소를 순회하고 종료

그리디 문제 중에서는 쉬운 편이였던 것 같다.

 

 

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

vector<ll> ar;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int tc, n;
	cin >> tc;

	for (int c = 1; c <= tc; c++) {
		ll sum = 0, maxVal = 0;
		cin >> n;
		ar.resize(n);
		for (int i = 0; i < n; i++) cin >> ar[i];

		maxVal = ar.back();
		for (int i = n - 2; i >= 0; i--) {
			if (ar[i] > maxVal) {
				maxVal = ar[i];
			}
			else {
				sum += maxVal - ar[i];
			}
		}

		cout << "#" << c << ' ' << sum << '\n';
	}

	return 0;
}