1859. 백만 장자 프로젝트

문제

SW Expert Academy

사재기를 해서 최대로 얻는 이익을 구하는 문제

3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

첫 날에 1을 1개 구매 = -1

두번째 날에 2를 1개 구매 = -2

따라서 총 -3을 지불하고

세번째 날에 값이 3으로 올랐으므로 가지고 있는 2개를 팔면 (2 * 3 = 6) 이다.

따라서 6 - 3 = 3의 이득을 봤다.

구매는 최대 1개만 할 수 있다(안살 수도 있음)

판매는 언제든지 판매가 가능하다.

 

처음에는 주어진 매매가를 처음부터 차례대로 보면서 계산을 하려했지만

다음과 같이 주어진 경우 (1 1 3 1 2) 계산을 하기가 어려웠다.

힌트를 얻었는데 거꾸로 판단하는 것이다.

int n;
cin >> n;
        ll sum = 0;
        for (int i = 0; i < n; i++)
            cin >> arr[i];

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

        cout << '#' << num << ' ' << sum << '\n';

정답이 들어갈 sum은 long long으로 선언하였다. 결과값이 100억을 넘을 수 있기 때문이다.

---

전체 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <cstring>
using namespace std;
int arr[1000001];
using ll = long long;
int main()
{
    int t;
    cin >> t;

    int num = 1;
    while (t--)
    {
        int n;
        cin >> n;
        ll sum = 0;
        for (int i = 0; i < n; i++)
            cin >> arr[i];

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

        cout << '#' << num << ' ' << sum << '\n';
        num++;
    }
    return 0;
}