1859. 백만장자 프로젝트 ( D2 ) - C++

이게 ... D2인데 LeetCode에서는 비슷한 문제가 아마 미디엄이었던가..?

Easy-Medium 수준이었던듯. 

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=CCPP&select-1=2&pageSize=10&pageIndex=1 

SW Expert Academy

 

# 풀이 

최대한의 이득을 얻도록 하자!
예를 들어 , 3일 동안의 매매가가 1,2,3 이라면, 처음 두 날은 다 구입을 하고,
(1,2) 마지막 날에 다 팔아버리면 (3-1) + (3-2) = 3의 이익을 얻는다. 

 

뒤부터 접근하면 된다. 뒤에서 부터 제일 큰 값을 찾으면서, 앞의 값을 빼주면서 합계로 더해주면 된다. 

int sell(vector<int>& aaa) {
    int res = 0;
    int a_len = aaa.size();
    int max_right = aaa[a_len-1];
    int sum = 0;
 
    for(int i = a_len-2; i >= 0; i--) {
        if(aaa[i+1] > max_right) max_right = aaa[i+1];
        if(max_right-aaa[i] > 0) { sum += (max_right-aaa[i]); }
    }
    
    return sum;
}