[백준 11501] - 주식(그리디?) C++

문제

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

11501번: 주식

접근방법

O(n*n)의 시간복잡도로는 해결하기 힘든 문제였다.

그리디 알고리즘이라고 생각하고 풀려고 했지만 잘 안 풀렸다.

 

결국 생각해낸 방법은 매수 매도 포인트를 미리 정해두는 것이다.

매일 하나씩 주식을 살 수 있으므로,

매도는 어차피 뒷 순서에 위치한 가장 큰 숫자에서 이루어질 수밖에 없다.

따라서 뒤에서부터 훑으며 매수 포인트와 매도 포인트를 구분할 수 있었다.

 

코드

//뒤에 보다 큰 숫자가 있는 경우 무조건 매수.
//뒤에 큰 숫자가 없다면 매수 X;
long long get_total(vector<int> price) {
    int maesu = -1, maesuCount = 0;
    long long total = 0;
    //매도 포인트 미리 지정.
    vector<bool> maesuPoint(price.size(), false);
    int tempPoint = price.size() - 1;
    for (int i = price.size() - 1;i > 0;i--) {
        if (price[tempPoint] > price[i-1]) {
            maesuPoint[i-1] = true;
        } else tempPoint = i-1;
    }
    FOR(i, price.size()) {
        if (maesuPoint[i]) {
            total -= price[i];
            maesuCount++;
        } else {
            total += (price[i] * maesuCount);
            maesuCount = 0;
        }
    }
    return total;
}

int t;
int main() {
    FASTERIO
    cin >> t;
    while(t--) {
        int n; long long answer;
        cin >> n;
        vector<int> price(n);
        FOR(i, n) {
            cin >> price[i];
        }
        cout << get_total(price) << "\n";
    }
    

    return 0;
}

개선할 점

테스트케이스가 좋아서 한 번에 맞출 수 있었다. 다행이다.

 

그래도 테스트케이스 한 개씩 직접 만들어서 해보고 제출하는 습관을 들이자.