[BOJ] 11501번 : 주식

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int t; 
int stocks[1000005], maxPrices[1000005];

int main(void) {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cin >> t; 
	while (t--) {
		int n; 
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> stocks[i]; 

		int maxPrice = INT_MIN;
		for (int i = n; i >= 1; i--) {
			maxPrice = max(maxPrice, stocks[i]);
			maxPrices[i] = maxPrice;
		}
		long long ans = 0;
		for (int i = 1; i <= n; i++) {
			if (maxPrices[i] > stocks[i]) ans += (maxPrices[i] - stocks[i]); 
		}
		cout << ans << '\n';
	}
}

오른쪽 인덱스부터 시작해서 최댓값을 기록하는 maxPrices arr를 만들었다. 따라서, 현재에서 앞으로 나아갈 때, 제일 먼저 만나는 최댓값을 O(n)으로 기록할 수 있다. 이 문제에서 greedy 한 방법을 사용할 수 있었던 이유는 무엇일까? 

증명방법은 생각이 안 난다. 단지, 그럴 것 같다는 느낌이 든다. 

 

3. solution 2 :

// Authored by : tongnamuu
// Co-authored by : -
// http://boj.kr/4b28aa2d9ef5448bb63d304f769f0c34
#include <bits/stdc++.h>
using namespace std;

int a[1000001];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int T;cin>>T;
  while(T--){
    int n;
    cin>>n;
    for(int i=0;i<n;++i) cin>>a[i];
    int max_val = a[n-1];
    long long ans = 0;
    for(int i=n-2;i>=0;--i) {
      if(a[i] > max_val) max_val = a[i];
      ans += max_val - a[i];
    }
    cout<<ans<<'\n';
  }
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x11/solutions/11501.cpp

basic-algo-lecture/0x11/solutions/11501.cpp at master · encrypted-def/basic-algo-lecture