[백준 11501번] 주식 (C++)

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

11501번: 주식

---

주식 문제에서는 매일 3가지 행동 중 한 행동을 할 수 있습니다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안 한다.

아래와 같은 동작을 생각해볼 수 있습니다. (단, stock[d]는 d일의 주식 가격)

1. stock[d] < stock[d+1]이면, 주식을 산다.
2. stock[d] > stock[d+1]이면, 주식을 판다.
3. stock[d] == stock[d+1]이면 아무것도 안 한다.

하지만, stock[d] > stock[d+1]이더라도 stock[d] < stock[m] 일 수 있습니다. (단, d < m)

즉, 주식이 다음날 떨어지더라도, 나중에 오를 수 있기 때문에 바로 팔지 않아도 나중에 수익을 낼 수 있습니다. 

 

따라서 아래와 같이 행동하면 최대 이익을 계산할 수 있습니다.

stock[d] < stock[m]인 m이 존재하면, d일에 주식을 사고 m일에 주식을 판다. (단, d < m)

 

하지만, 매번 d일 이후에 stock[d] < stock[m]인 m이 존재하는 지 확인하면 시간 복잡도가 O(N²)입니다.

하지만, n이 최대 1,000,000이기 때문에 이러한 방식의 경우 시간 초과가 발생할 수 있습니다.

 

따라서 d부터 n - 1일까지일 중 가장 주가가 높은 날을 저장하는 배열을 만들어주어야 합니다.

 

또한, 최대 이익은 int형을 벗어나므로 long long형을 사용해야합니다. (ex. 1 1 1 ... 10000)

 

아래는 전체 코드입니다.

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

long long stock[1000010];

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

    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        fill(stock, stock + n, 0);
        for(int i = 0; i < n; i++) cin >> stock[i]; // 날 별 주가 입력 받음.

        int m[1000010];   // m[d]는 m[d]부터 m[n - 1]까지 중 가장 큰 수의 idx를 저장
        m[n - 1] = n - 1;
        for(int day = n - 2; day >= 0; day--){  // m 배열 채워줌
            if(stock[day] > stock[m[day + 1]]) m[day] = day;
            else m[day] = m[day + 1];
        }

        long long ans = 0;
        for(int day = 0; day < n; day++){
        	// stock[d] < stock[m]인 m이 존재하면, d일에 주식을 사고 m일에 주식을 판다.
            if(stock[day] < stock[m[day]])  
                ans+= stock[m[day]] - stock[day];
        }
        cout << ans << "\n";
    }
}