SWEA - 백만 장자 프로젝트 (C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

그리디 문제로 보인다. N이 백만이지만 제한 시간을 30초나 주기 때문에 엄청나게 빡빡하진 않다고 본다.

 

먼저 예제에 없는 유형을 보자

 

1 7 2 10

 

이 때 최상의 경우는 1 7 2에서 모두 사고 10에서 파는 것이다. 즉, 올라가다가 내려간다고 팔면 최적이라 볼 수 없다. 그래서 계속 이후 앞에 최대값이 얼마나 있을지 생각해야한다. 난 그래서 처음 최대값을 설정하고 최대값을 만났을 때 팔고 이후 반복문을 돌리며 남은 숫자 중 최댓값을 찾는 식으로 작성하였다.

 

시간초과가 날 것같았는데 생각보다 적은 시간에 풀이가 됐다. 그러나 1ms에 푼 사람도 있는 것을 보면 O(N) 으로 dp나 다른 방법이 있는듯하다. 

 

그리고 백준 11501 주식과 같은 문제인데, 이 문제에선 시간초과가 난다... 좀 더 최적화 해봐야겠다.

 

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

int main(){
    int T; cin >> T;

    for(int t = 1; t <= T; t++){
        int N;
        long long answer = 0;
        cin >> N;

        vector<int> bucket;
        vector<int> values(N);
        int maxValue = 0;
        for(int i = 0; i < N; i++){
            cin >> values[i];
            maxValue = max(maxValue, values[i]);
        }

        for(int i = 0; i < N; i++){
            if(maxValue == values[i]){
                for(int j = 0; j < bucket.size(); j++){
                    answer += (maxValue - bucket[j]);
                }
                maxValue = 0;
                for(int j = i + 1; j < N; j++){
                    maxValue = max(maxValue, values[j]);
                }
                bucket.clear();
            }else{
                bucket.push_back(values[i]);
            }
        }

        cout << '#' << t << ' ' << answer << '\n';
    }
}