[백준/boj] 11501번: 주식 | C++

재귀 - 시간초과

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

int t;

long long val[1000002];//날별 주가
int valNum;
long long profit;

void func(int str){
    if(str>=valNum-1) return;
    int maxIDX= max_element(val+str,val+valNum)-val; //맥스값의 인덱스 받음
    if(maxIDX==str) {
        func(maxIDX+1);
        return;
    }
    long long maxNum = val[maxIDX];
    for(int i =str;i<maxIDX;i++){
        long long p =maxNum - val[i];
        profit += p; //이전에 나보다 낮은 값들에 대해 차익 다 더함
    }
    func(maxIDX+1);
}

    //오를때는 사고, 제일 고점일때 다 팔고. 차익을 더한게 최종 이익이되고
    //고점이 또 있으면 그 고점보다 하나라도 벨류 낮아지는 날부터 사고

    //가장 높은 고점 하나 구해 -> 그날 이전 기준으로 그것보다 벨류가 낮은날에는 다 사고 아닌날에는 가만히. 가장 높은 고점날 팔기//
    //현재+1부터 마지막까지 가장 높은 고점 구해-> 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;

    while(t--){
        int n;
        cin>>n;
        valNum =n;
        profit =0;
        for(int i=0;i<n;i++){
            cin>>val[i];
        }   
        func(0);
        cout<< profit<<'\n';
        
    }
    
}

 

배열 뒤부터 돌면서 max 값 갱신하는 방법 - 성공

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int arr[1000002];


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >>t;
    while(t--){
        int n;
        cin >> n;
        ll sum=0;
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }

        int max = 0;
        for(int i=n-1;i>= 0;i--){
            if(arr[i]<max){
                sum += max - arr[i];
            }else{
                max = arr[i];
            }
        }
        cout <<sum<<'\n';
    }
}