SWEA 1859. 백만 장자 프로젝트

• 문제 링크 : 1859. 백만 장자 프로젝트

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

문제 설명

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다. 다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다. 다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.

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

1. 문제 해석

2. 문제 풀이

#include <iostream>
using namespace std;
int N;
int price[1000000];
long long solution(){
    long long answer=0;
    int max_price=price[N-1], sum=0, count=0;
    for(int i=N-2;i>=0;--i){
        if(price[i]>=max_price){
            answer += max_price * count - sum;
            max_price=price[i];
            count=0; sum=0; continue;
        }
        count++;
        sum+=price[i];
        if(i==0){
            answer += max_price * count - sum;
        }
    }
    return answer;
}

int main(int argc, char** argv) {
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case) {
        cin >> N;
        for(int i=0;i<N;++i){
            cin >> price[i];
        }
        cout << "#" << test_case << " " << solution() << "\n";
    }
    return 0;
}