문제

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

풀이

오답: O(NlogN)

현재 이후로 주가가 오르는 날이 하루라도 있으면, 현재 주식을 사둔 다음

주가가 오르는 날에 갖고 있던 주식을 모두 파는 식으로 구현해봤다.

그런데 오답이라고 한다 :(

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

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

  int T;
  cin >> T;

  while (T--) {
    int N;
    cin >> N;

    vector<int> stocks;
    for (int i = 0; i < N; i++) {
      int x;
      cin >> x;
      stocks.push_back(x);
    }

    long long total = 0;
    int buyNum = 0;

    for (int i = 0; i < N; i++) {
      int currentStock = stocks[i];
      auto it = upper_bound(stocks.begin() + i + 1, stocks.end(), currentStock);

      // 현재보다 주가가 더 오르는 날이 있으면
      if (it != stocks.end()) {
        // 현재 주식을 사둔다. (비용 증가)
        total -= currentStock;
        buyNum++;
      } else {
        // 갖고 있는 주식이 없으면 total 값 그대로 유지
        if (buyNum == 0)
          continue;

        // 갖고 있는 주식이 있으면 현재 주가로 판다.
        total += currentStock * buyNum;
        buyNum = 0;
      }
    }

    cout << total << "\n";
  }

  return 0;
}

생각의 전환: O(N)

뒤에서부터 앞으로 배열을 탐색하며 현재보다 주가가 떨어지면, 현재 주가와 떨어진 주가 사이의 차이를 계산하여 최대 이익을 구할 수 있다.

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

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

  int T;
  cin >> T;

  while (T--) {
	  int N;
	  cin >> N;
	  
	  vector<int> stocks;
	  for (int i = 0; i < N; i++) {
		  int x;
		  cin >> x;
		  stocks.push_back(x);
	  }

	  long long total = 0; 
	  int currentMax = -1; 
	  
	  for(int i = N - 1; i >= 0; i--){
		  currentMax = max(stocks[i], currentMax); 

		  // 최댓값보다 현재 주가가 낮으면 그 차이값이 이익이 된다. 
		  total += currentMax - stocks[i];
	  }

	  cout << total << "\n"; 
  }

  return 0;
}