14943 벼룩시장

그리드하게 풀었다.

처음 풀 때는 값이 변할 때 index, 위치를 기억해야 한다고 생각해서 deque로 풀었다.

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
 
int n;
long long score;
deque<pair<int, int>> q;
 
int main() {
    scanf("%d", &n);
    for (int i = 0, t; i < n; i++) {
        scanf("%d", &t);
        if (q.empty()) q.push_back({ t,i });
        else {
            int ind = 0, pre = t;
            //  1  0 < t < 0  0
            bool f = false;
            if (q.front().first * t < 0) {
                if (t > 0) f = true;
                while (q.size() && pre*t > 0) {
                    pre = t;
                    score += min(abs(q.front().first), abs(t)) * abs(i - q.front().second);
                    t += q.front().first;
                    ind = q.front().second;
                    q.pop_front();
                }
                if ((f && t > 0) || (!f && t < 0)) q.push_back({ t,i });
                else if ((f && t < 0) || (!f && t > 0)) q.push_front({ t,ind });
            }
            else if (t) q.push_back({ t,i });
        }
    }
    printf("%lld", score);
    return 0;
}

그런데 다른분들 코드를 보니 어마어마하게 간단하게 푸셨다.

(사는곳 위치 - 파는곳 위치)*갯수 가 맞긴 한데 위치를 한번에 계산하는게 아니라 매번 위치를 옮길때마다

패널티가 쌓이는 방식으로 생각하니 간단했다.

예를들어

5

500 0 0 0 -500

이 입력되면

500*4를 한번에 계산하는게 아니라

500 500 500 500 0

이렇게 인덱스가 지나갈 때마다 이전에 처리하지 못한 물량이 패널티가 되어 쌓이는 방식으로 생각하면 코드가 말도안되게 간단해진다.