SW Expert Academy 1859. 백만장자 프로젝트 D2

문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

D2문제임에도 불구하고 조금 까다로웠던 문제이다.

처음에 문제를 풀때는 priority_queue에 pair형식으로 인덱스와 매매가를 함께

넣어주어 매매가가 높은 index까지 계속 차액을 더해주고 해당 index해 도달하면

그 뒷 배열에 있는 것중 매매가가 가장 높은 곳까지 차액을 더해주는 식으로

문제를 풀었다.

결과적으로 테스트 케이스중 5개만 맞았는데 절차는 맞으나 복잡도나 공간의 문제가 

생겼던걸로 보인다.

---

간단하게 푸는 방식은 마지막 index부터 처리하는 것이다.

마지막 index부터 처음 나오는 가격보다 높은 가격이 나올 때까지 차액을 더해주는 방식을

계속 해주면 O(N)의 복잡도로 문제를 풀 수 있다.

#include <iostream>
 
using namespace std;
 
int arr[1000001];
int main()
{
    int T;
    scanf("%d",&T);
    for(int i=1; i<=T; i++){
        long long ans = 0;
        int N;
        scanf("%d",&N);
        for(int j=0; j=0; k--){
            if(x > arr[k])
                ans += x - arr[k];
            else
                x = arr[k];
        }
        printf("#%d %lld\n",i,ans);
    }
}