11501번: 주식

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

11501번: 주식

0번째 날부터 N - 1번쨰 날 중 주식의 가격이 p번째 날에 가장 크다고 하자. 0번째 날부터 p - 1번째 날까지는 주식을 산 뒤, p번째 날에 주식을 팔면 0번째 날부터 p번째 날까지 최대 이득을 볼 수 있다. 이제 p + 1번째 날부터 N - 1번째 날 중 주식의 가격이 q번째 날에 가장 크다면, 다시 p + 1번째 날부터 q - 1번째 날까지는 주식을 산 뒤, q번째 날에 팔면 p + 1번째 날부터 q번째 날까지 최대 이익을 볼 수 있다.

이 과정을 각 최댓값 별로 구역을 나눠 모든 구역에 대해 실행하면 최대 이익을 볼 수 있다. 단 최댓값을 구하는 데에 O(N) 시간이 걸리므로, 최악의 경우 각 테스트 케이스마다 O(N ^ 2)시간이 걸리게 된다. 따라서 0번째 날부터 시작하는 것이 아니라 N - 1번째 날부터 시작해 현재 날의 가격이 최대라면 최댓값을 갱신하고, 그렇지 않다면 최댓값에서 현재 가격을 뺀 값만큼 이득을 보았다고 간주해 계산하면 각 테스트 케이스마다 O(N) 시간 안에 답을 구할 수 있다.

#include <iostream>

using namespace std;

typedef long long ll;

#define MAX_N 1000000

// 각 테스트 케이스를 입력받아 정답을 반환
ll test_case() {
    // 주가 배열의 길이
    int N;
    // val[i]: i번째 날의 주가, max: 팔았을 때 최대 이익을 볼 수 있는 주가
    short val[MAX_N] = { 0, }, max = 0;
    // ret: 실현손익
    ll ret = 0;

    // 주가 배열을 입력받은 뒤
    cin >> N;
    for (int i = 0; i < N; i++) cin >> val[i];
    // 마지막 날부터 역순으로
    for (int i = N - 1; i >= 0; i--) {
        // 주가의 최대치를 발견한다면 매도일을 i번째 날로 지정
        if (max < val[i]) max = val[i];
        // 그렇지 않다면 주식을 사 지정한 매도일에 주식을 매도
        else ret += max - val[i];
    }

    // 실현손익을 반환
    return ret;
}

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
    // 테스트 케이스의 수를 입력받고 각 테스트 케이스의 정답을 출력
    for (cin >> T; T--; ) cout << test_case() << '\n';
    return 0;
}