[SWEA] 1859. 백만 장자 프로젝트 c++

• 문제

    1. 연속된 N일 동안의 물건의 매매가가 주어진다.
    2. 하루에 최대 1만큼 구입할 수 있다.
    3. 판매는 얼마든지 할 수 있다.

 

• 입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

각 날의 매매가는 10,000이하이다.

 

• 출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

 

• 문제 해결

1. N일 동안의 물건의 매매가를 vector에 저장한다. (N일 동안의 물건의 매매가를 알고 있다는 가정이므로)

2. vector  뒤에서 부터 검사한다.

3. 뒤에서 부터 검사하므로, max 보다 작으면 물건을 판다.

   ex ) 3 5 9 → 9 5 3

         max = 9

         9-5 = 4, 9-3 = 6

         4 + 6 = 10

 

  

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

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
        int n = 0;
        cin >> n;
        vector<int> vec(n, 0);
        for(int i = 0; i < n; i++){
        	cin >> vec[i];
        }
        long long price = 0;
        int nMax = vec[n-1];
        for(int i = n - 2; i >= 0; i--){
        	nMax = max(nMax, vec[i]);
            price += nMax - vec[i];
        }
		cout << "#" << test_case << " " << price << endl;
	}
	return 0;
}