[C++/SWEA] 1859: 백만 장자 프로젝트

✅ D2
🔖 구현

✏️ 1차 솔루션

max_element 함수 활용

1. max_element 함수로 최대 매매가 계산 ➡️ 첫번째 최대 매매가
2. 최대 매매가 이전까지 계속 구매하고 최대 매매가일 때 매도
3. 매도하고 나서는 최대 매매가를 갱신

🚨 1차 trouble

• max_element 로 전체 영역의 최대 값을 찾을 수는 있지만 특정 영역의 최대값을 찾기에는 부적합
• 매도 이전에 구입한 개수가 몇 개인지, 구입 가격은 얼마인지 따로 저장해야 해서 변수 낭비가 심한 듯?

✏️ 최종 솔루션

1. 맨 끝 매매가를 최대 매매가로 저장
2. 맨 끝 매매가부터 탐색 시작
   1) 최대 매매가보다 작을 경우, 최대 매매가 - 해당 매매가 를 answer(이익) 에 더하기
   2) 최대 매매가보다 크거나 같을 경우, 새로운 최대 매매가로 갱신

📌 self feedback

• 알 수 없는 오류 나면 int 자료형 long long 으로 바꿔보기
• 변수나 벡터 초기화 필수!

✏️ 최종 code

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int test_case=1;
	int T;
    vector<int> cost; 
    
	cin>>T;
    
    while(T--) {
        int N;
        cin >> N;
        
        int k;
        for(int i=0;i<N;i++) {
            cin >> k;
            cost.push_back(k);
        }

        cout << "#" << test_case << " ";
        test_case++;
        
       long long total=0;		//이익 총합

        int mx=cost[N-1];	//최대 매매가
        for(int i=N-2;i>=0;i--) {
            if(mx>cost[i])  total+=(mx-cost[i]);
            else mx=cost[i];

        }
      
          cout << total << endl;

        while(!cost.empty()) {
            cost.pop_back();
        }
    }
	return 0;
}