1859 - 백만 장자 프로젝트

문제

• SW Expert Academy 참고

풀이

그리디 알고리즘 문제였다. 풀이를 하면서 주의할 점은 최대 이익이 int값의 범위를 초과할 수 있다는 점이다.

(대략 최대 100억)이 정답으로 나올 수 있기 때문에 long long 자료형을 함수의 반환값으로 지정하였다.

핵심 아이디어는 가격 벡터 탐색 시 뒤에서 부터 탐색하는 것이다. 미래의 날중 가장 높은 가격을 찾은 후 탐색 중 가격이 낮은 날이면 물건의 차익을 계산하고 총합을 반환하여 출력하였다.

 

#include<iostream>
#include<vector>
using namespace std;
int T,N;
vector<int> price;
long long getProfit(){
    long long ans = 0;
    int maxPrice = price.back();
 
    for (int i = N - 2; i >= 0; i--) {
        if (price[i] > maxPrice) {
            maxPrice = price[i];
        } else {
            ans += (maxPrice - price[i]);
        }
    }
 
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>T;
    for(int k=0;k<T;k++){
        int t;
        cin>>N;
        for(int i=0;i<N;i++){
            cin>>t;
            price.push_back(t);
        }
        cout<<"#"<<k+1<<" "<<getProfit()<<"\n";
        price.clear();
    }
 
}