백준 10800 (C++) 컬러볼

최초 업로드: 2025-11-06 10:04:45

최근 수정 시간: 2025-11-06 10:04:45

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 컬러볼

[문제 링크](https://www.acmicpc.net/problem/10800)

## 문제 설명

<p>지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다.</p>

<p>공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 출력하는 프로그램을 작성하시오. </p>

## 입력

## 출력

<p>N개의 줄을 출력한다. N개의 줄 중 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.</p>

## 풀이
공의 크기 기준으로 정렬하여, 같은 크기는 축적해놓고 한번에 업데이트 하고, 누적된 작은 공들의 크기 합을 오프라인으로 저장해뒀다가 출력해주면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct element {
    int c, s, idx;
    bool operator<(const element e) const {
        return s<e.s;
    }
};

ll total, cnt[200'001], res[200'000];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<element> v(n);
    for(int i=0;i<n;i++) {
        cin >> v[i].c >> v[i].s;
        v[i].idx=i;
    }
    sort(v.begin(), v.end());

vector<element> stk;
    for(auto e:v) {
        if(!stk.empty() && stk.back().s<e.s) {
            while(!stk.empty()) {
                cnt[stk.back().c] += stk.back().s;
                total += stk.back().s;
                stk.pop_back();
            }
        }
        res[e.idx] = total-cnt[e.c];
        stk.push_back(e);
    }
    for(int i=0;i<n;i++) cout << res[i] << '\n';
}
```