백준 11501. 주식

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

11501번: 주식

 

일단 주식은 가격이 낮을때 사서 높을때 팔아야한다.

따라서 오늘 구입하는 시점 이후에 가장 높을때 팔면된다.

input이 만약 다음과 같다면

 

day	1	2	3	4	5	6
price	3	5	8	1	7	6

 

1일 이후 가장 가격이 높은날은 3이다.

1일날 사고, 2일날도 사고, 3일날 팔면된다. 

그렇게 되면 이익이 (8-3)+(8-5) = 8 이다.

 

그후 4일날 이후 가장 비싼 날이 5일이다.

(7-1) = 6

 

이렇게하면 전체 이득은 14가된다.

그런데 문제는 이렇게 계산하게 되면 오늘 이후 가장 비싼때가 언제인지 모르기 때문에 

가장 비싼날을 계속해서 탐색해야 한다.

 

---

이 문제는 뒤에서부터 계산하면 한번의 탐색 O(n)으로 끝낼수 있다.

마지막 날에서 부터 첫날로 이동한다.

 

i날이 최대가격보다 가격이 높다면 : 최대가격 갱신

i날이 최대가격보다 가격이 낮다면 : 판다 (이때 판다는것은 i날에 파는것이 아니라 i날에 사서 최대가격날 파는것이다)

 

 

day	1	2	3	4	5	6
price	3	5	8	1	7	6

 

6일:

맨 뒤에서 부터 계산하면 6일날에 최대가격 = 6

 

5일:

최대가격=6 보다 크므로 최대가격=7로 갱신

 

4일:

최대가격=7보다 작으므로 4일날 산것을 최대가격인 5일날 팜.

(7-1) = 6

 

3일:

최대가격=7 보다 높으므로 최대가격=8

 

2일:

최대가격 보다 낮으므로 

(8-5) = 3

 

1일:

최대가격 보다 낮으므로

(8-3) = 5

 

총 이익:

(7-1) + (8-5) + (8-3) = 6 + 3 + 5 = 14

 

#include <iostream>
#include <vector>
using namespace std;


//int stock[1000001];

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

    int tc;
    cin >> tc;

    while(tc--)
    {
        int n;
        vector<long long> stock;
        long long profit = 0;

        cin >> n;
        stock.resize(n);
        for(int i = 0; i < n; i++)
        {
            cin >> stock[i];
        }


        // 뒤에서부터 앞으로
        long long highest = stock[n-1];
        for(int i = n-2; i >= 0; i--)
        {
            if(stock[i] > highest)
            {
                highest = stock[i];
            }
            else
            {
                profit += highest - stock[i];
            }
        }

        cout << profit << '\n';
    }




}