[ICPC] 백준 11501 - 주식

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

힌트(시간 초과 관련)

이 문제는 $O(N)$으로 풀 수 있다.

 

당신은 이미 계산했던 날을 다시 거쳐갈 필요가 없음을 상기하라.

---

풀이

각 날마다 주식의 가격이 주어졌을 때 최대 이득을 취하는 방법을 찾아야 한다.

 

우리는 이미 어느 날에 가격이 높은지 알고 있다. 다음 개형을 보자.

 

이런 형태에서는 1~2일에 매수하고 3일에 매도, 4~5일에 매수하고 6일에 매도하는 게 최적해가 됨을 단박에 알 수 있다. 다음 개형도 보자.

 

 이런 경우는 1~5일까지 매수를 하다가 6일에 전부 매도하는 게 최적해가 된다.

 

이 두 개형을 통해 우리는 주식 가격의 극대 값에 도달하기 전까지 매수를 해야 함을 발견할 수 있다.

 

그렇다면 이를 어떻게 구현해야 할까?

 

각 가격에 해당하는 index를 배열로 관리 후 큰 가격의 큰 index부터 낮은 index로 스위핑을 하면 $O(N)$의 시간 복잡도로 해결할 수 있다.

 

그렇게 되면 가장 큰 가격의 가장 큰 index부터 스위핑을 하게 되면 만나게 되는 가격은 자신보다 작거나 같음이 자명하고 가격의 차이를 더해나가면 된다.

 

하지만 이렇게 하면 낮은 가격의 index를 스위핑할 차례가 올 때 자신보다 큰 가격을 만날 수 있지 않느냐는 의문이 들 수 있다.

 

이는 방문한 날짜를 관리하는 배열을 두어 간단히 해결할 수 있다.

 

어떤 날짜를 방문했을 때 그 날짜가 이미 방문되었다는 것은 현재 스위핑을 하는 가격보다 큰 가격의 주식이 계산을 끝마쳤다는 의미가 된다. 그러면 당연히 그 이전의 날짜도 이미 계산되었다는 것도 알 수 있다.

 

따라서 스위핑을 하면서 이미 방문한 날짜를 마주치면 바로 break를 해서 효율적으로 계산할 수 있다.

 

이렇게 모든 가격에 대해 스위핑을 하면서 계산한 이익의 총합을 출력하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int t;
bool visited[1000000];
int ar[1000000];
vector<int> idx[10001];

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

  cin >> t;

  while (t--)
  {
    ll res = 0;

    memset(visited, 0, sizeof visited);
    for (int i = 0; i <= 10000; ++i)
      idx[i].clear();
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i)
    {
      cin >> ar[i];
      idx[ar[i]].push_back(i);
    }

    for (int i = 10000; i > 0; --i)
    {
      if (idx[i].empty())
        continue;
      
      for (int j = idx[i].size() - 1; j >= 0; --j)
      {
        int pos = idx[i][j];
        if (visited[pos])
          continue;
        
        visited[pos] = true;
        --pos;

        while (pos >= 0)
        {
          if (visited[pos])
            break;
          
          res += i - ar[pos];
          visited[pos] = true;
          --pos;
        }
      }
    }

    cout << res << '\n';
  }
}

제출 기록