[백준 14943번] 벼룩 시장 (C++)

문제링크 : https://www.acmicpc.net/problem/14943

14943번: 벼룩 시장

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll arr[100001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    ll N;
    cin >> N;

    ll sum = 0;
    ll result = 0;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        sum += arr[i]; //현재 적재량
        result += abs(sum); //배달하는 양 더하기
    }

    cout << result;


    return 0;
}

문제에서 사람들이 사려고 하는 벼룩의 합과 파는 벼룩의 합은 같다라고 명시되어있고, 거리가 멀수록 비용이 증가하므로 처음부터 거리가 가장 가까운 순서대로 배달하면 된다.

 

<예제>
5
500 -200 -400 50 50

위 예제로 살펴보면,

i = 0 : 500 판매 -> 배달량 500 

i = 1 : 200 구매 -> 배달량 300 (비용 500)

i = 2 : 400 구매 -> 배달량 -100 (미리 100개 땡겨구매 -> 총합은 결국 같기 때문에 가능) (비용 800)

i = 3 : 50 구매 -> 배달량 -50 (비용 900)

i = 4 : 50 구매 -> 배달량 0 (비용 950)

 

따라서 총 비용은 950이 된다.