백준 10800번 컬러볼 - C++ 풀이

 

---

 

1. 공들을 크기 오름차순으로 정렬한다.
2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합)

 

1. 공들을 크기 오름차순으로 정렬한다.

 먼저 공들을 크기 기준으로 오름차순 정렬해준다.

 

2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합)

 i번째 공보다 크기가 작고 색이 달라야 하므로, (i번째 공보다 작은 공들) - (i번째 공보다 작고 색이 같은 공들)을 구하면 된다. 포인터를 하나 두고, 포인터가 가리키는 공의 크기가 현재 공의 크기와 같아지기 전까지 포인터를 오른쪽으로 이동시키면서 1. 전체 크기 합과 2. 색깔별 크기 합을 계산한다. 즉, 현재 공보다 작은 모든 공들에 대해 전체 크기 합과 색깔별 크기 합을 구해둔다. 포인터 이동을 마쳤으면 전체 크기 합에서 현재 공과 같은 색인 공들의 크기 합을 빼주면 현재 공이 사로잡을 수 있는 공들의 크기합을 구할 수 있다.

반응형

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct {
    int sz, color, idx;
} Ball;

int N;
vector<Ball> balls;

bool cmp(const Ball& lhs, const Ball& rhs) {
    if (lhs.sz != rhs.sz) return lhs.sz < rhs.sz;
    if (lhs.color != rhs.color) return lhs.color < rhs.color;
    return lhs.idx < rhs.idx;
}

vector<int> solution() {
    vector<int> ans(N, 0);
    vector<int> color_sum(N+1, 0);   // color_sum[color] = color색인 공들의 사이즈 합
    int i = 0;
    int total_sum = 0;
    
    // 사이즈 오름차순 정렬
    sort(balls.begin(), balls.end(), cmp);
    
    for (auto ball: balls) {
        // ball보다 작은 모든 공들에 대해
        while (balls[i].sz < ball.sz) {
            Ball small_ball = balls[i];
            total_sum += small_ball.sz;
            color_sum[small_ball.color] += small_ball.sz;
            i++;
        }
        
        // (ball보다 작으면서 다른 색의 공들) = (ball보다 작은 모든 공들) - (ball보다 작으면서 같은 색의 공들)
        ans[ball.idx] = total_sum - color_sum[ball.color];
    }
    
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        int c, s;
        cin >> c >> s;
        balls.push_back({s, c, i});
    }
    
    auto ans = solution();
    for (auto x: ans) cout << x << "\n";

    return 0;
}