[그리디 #1] BOJ 11501 주식

https://www.acmicpc.net/problem/11501

11501번: 주식

 

그리디를 오늘부터 제대로 시작해보려고 한다.

먼저 이 문제를 고르게되었다.

 

그리디 알고리즘이 '현재에서 가장 Best인 항목을 선택' 하기에 이번에도 이를 적용하려고 하였다.

 

첫번째 시도

고수익을 얻기 위해선 무조건 최고점일 때 판매를 해야한다.

최고점을 구하는 함수를 만들어 이를 사용하였다.

테스트 케이스 중 1 1 3 1 2 의 경우, MAX가 3이기 때문에 고점을 고정하여 진행하게 되면 3 다음 1, 2에서 아무런 작업도 수행하지 않기에 4라는 결과가 나온다. (정답 5)

 

따라서, MAX에서 판매 후 고점을 새로 구하는 함수를 이용한 것이다.

 

이 방법을 이용하면, 테스트케이스 Loop 까지 포함하여 총 O(N^3)의 시간이 걸리기에 시간 초과가 나온다.

 

두번째 시도

고점을 매번 구하지 않고 진행하는 방법을 생각해보았다. 역순으로 진행 시 고점 선정과 판매가 유리하여 이를 이용하자.

 

1 1 3 1 2를 이용해보자.

 

1) 2

 마지막 날은 무조건 판매해야 하기에 MAX를 2로 두자.

 

2) 1

 MAX보다 작은 값이므로 판매하는 행동을 한다.

이때 수익은 MAX - Current 이다.

 

3) 3

 MAX보다 큰 값이 왔기 때문에, 이전의 MAX(정방향으로 보았을 때)값이므로 업데이트한다.

 

4) 1

 MAX보다 작은 값이기에 판매한다.

 

5) 1

 MAX보다 작은 값이므로 판매한다.

 

따라서, 알고리즘을 요약하면 다음과 같다.

 

1. MAX < Current

- 이전의 MAX이므로 MAX = Current

 

2. 나머지 경우

- MAX에서 판매하는 주이므로, sum += MAX - Current

 

 

코드

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int arr[1000001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}


		int large = -1;
		long long sum = 0;
		for (int cur = n; cur >= 1; cur--) {
			if (large < arr[cur]) {
				//cout << "changed: " << large << endl;
				large = max(large, arr[cur]);
			}
				
			else if (large >= arr[cur]) {
				int tmp = large - arr[cur];
				sum += tmp;
			}
		}

		cout << sum << "\n";
	}


}

 

[ 참고 ]