BOJ 10800 C++

코드 원리

이 코드는 다음과 같이 동작합니다.

color와 scale 배열은 각각 공의 색깔과 크기에 따라 크기의 합을 저장하기 위한 배열입니다. 초기값은 0으로 설정됩니다.

info 구조체는 공의 색, 크기, 인덱스, 누적 크기 합, 정답을 저장하는 구조체입니다.

입력받은 공들의 정보를 balls 벡터에 저장하고, 공의 크기와 색깔에 따라 정렬합니다.

각 공에 대해 누적 크기 합과 정답을 계산합니다. 누적 크기 합은 이전 공들의 크기 합에 현재 공의 크기를 더한 값입니다. 색깔과 크기에 따라 누적된 크기를 빼주어야 하는데, 이를 위해 color 배열과 scale 배열을 사용합니다. 만약 현재 공의 색깔과 크기가 이전 공과 동일하다면, 정답은 이전 공의 정답과 동일합니다.

balls 벡터를 인덱스 순서대로 정렬하여 정답을 출력합니다.

이 코드는 입력에 따라 공들의 크기 합을 계산하고 출력합니다.

코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;
int color[200001];  // 각 색깔의 공들의 크기의 합을 저장하기 위한 배열
int scale[2001];  // 각 크기의 공들의 크기의 합을 저장하기 위한 배열

struct info
{
    int c, s, i, sum, ans;  // 공의 색, 크기, 인덱스, 누적 크기 합, 정답을 저장하는 구조체
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    vector<info> balls(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> balls[i].c >> balls[i].s;
        balls[i].i = i;
    }
    
    // 공을 크기와 색깔에 따라 정렬
    sort(balls.begin(), balls.end(), [](const info& x, const info& y) {
        if (x.s == y.s)
            return x.c < y.c;
        return x.s < y.s;
    });
    
    for (int i = 1; i <= n; i++)
    {
        balls[i].sum = balls[i - 1].sum + balls[i].s;  // 누적 크기 합 계산
        color[balls[i-1].c] += balls[i - 1].s;  // 이전 공의 색깔에 해당하는 크기 추가
        scale[balls[i-1].s] += balls[i - 1].s;  // 이전 공의 크기에 해당하는 크기 추가
        balls[i].ans = balls[i].sum - color[balls[i].c] - scale[balls[i].s] - balls[i].s;  // 정답 계산
        if (balls[i - 1].c == balls[i].c && balls[i - 1].s == balls[i].s)
            balls[i].ans = balls[i-1].ans;  // 같은 크기와 색깔을 가진 공의 정답은 이전 공의 정답과 동일
    }
    
    // 인덱스 순서대로 정렬하여 정답 출력
    sort(balls.begin(), balls.end(), [](const info& x, const info& y) {
        return x.i < y.i;
    });
    
    for (int i = 1; i <= n; i++)
    {
        cout << balls[i].ans << "\n";
    }
    return 0;
}