10800번 컬러볼

https://www.acmicpc.net/problem/10800

백준 boj colorball 복습 필수 코딩테스트 코테 추천 Greedy 그리디 탐욕 탐색 배열활용

우선 내가 생각한 정답은 (집합이라고 생각하면 된다)

답 = 

누적된 크기의 합 - (자신의 컬러에 맞는 크기의 합 + 자신하고 같거나 큰 크기들의 크기의 합) + 자신과 똑같은 칼라에서 자신의 크기와 같거나 그 이상의 크기들의 합

이라고 생각하였다. 계산된 식이 음수가 나오면, 0을 출력한다.

누적된 크기의 합 = sum

자신의 컬러(c)에 맞는 크기의 합 = color[c]

자신의 크기(s)보다 큰 크기들의 크기의 합 = clm[max_size] - clm[s - 1]

자신과 똑같은 칼라에서 자신의 크기와 같거나 그 이상의 크기들의 합 = same_vector[c]에서 그냥 for문으로 구해준다.

여기서 clm은 누적합을 사용한다.

아마 누적합이 아니면, 시간 초과가 발생할 것 같다.

그러나 내 코드는 O(n^2)이고 비효율적이다.

같은 색깔의 공들이 많을 경우 시간 초과가 발생할 것인데, 데이터가 약해서 통과됐다.

정답자 분들 중 한 분(koosaga님)님의 코드를 참고하였다.

핵심은 '크기'를 기준으로 구현하는 것인데, 자세한 것은 두 번째 코드를 참고.

O(n^2)

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 200002
 
int n, sum, color[Max], clm[Max / 100 + Max % 10];
vector<pair<int, int> > v;
vector<int> same_color[Max];
 
bool cmp(const int & a, const int & b)
{
    return a > b;
}
 
int same(int c, int s)
{
    int ret = 0;
 
    for (auto i : same_color[c]) {
        if (i < s) { // s보다 작으면 바로 종료
            break;
        }
        ret += i;
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
 
    int c, s, max_size = 0, max_color = 0;
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &c, &s);
        v.push_back({ s, c }); // { 크기, 색깔 }
        sum += s; // 크기의 총 합
        color[c] += s; // color[c] : c 색의 크기(s)의 총합
        clm[s] += s; // clm[s] : s 크기에 해당하는 크기(s)의 총합
        max_size = max(max_size, s); // 변수 활용해야함. 크기(s)의 최댓값.
        same_color[c].push_back(s); // 같은 색깔(c)에 해당하는 s의 집합
        max_color = max(max_color, c);
    }
 
    // 누적합 : cumulative sum (clm)
    for (int i = 1; i <= max_size; i++) {
        clm[i] += clm[i - 1];
    }
 
    // 같은 색깔 안에서 내림차순 정렬
    for (int i = 1; i <= max_color; i++) {
        if (!same_color[i].empty()) {
            sort(same_color[i].begin(), same_color[i].end(), cmp);
        }
    }
 
    for (auto i : v) {
        // 답 : 총 크기의 합 - (같은 색깔에 해당하는 크기의 합 + 자신의 크기(s)보다 같거나 큰 크기들의 누적 크기 합)
        int answer = sum - (color[i.second] + clm[max_size] - clm[i.first - 1]);
        answer += same(i.second, i.first);
        printf("%d\n", answer);
    }
    
    return 0;
}

O(nlogn)

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 200002
 
typedef struct info {
    int Color, Size, Index;
}info;
 
int n, ans[Max], sum[Max], total;
vector<info> v;
 
bool cmp(const info & a, const info & b)
{
    return a.Size < b.Size;
}
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
 
    int c, s;
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &c, &s);
        v.push_back({ c, s, i });
    }
 
    // 크기(s) 기준으로 오름차순 정렬
    sort(v.begin(), v.end(), cmp);
 
    int vs = v.size();
 
    for (int i = 0; i < vs; i++) {
        int idx = i;
 
        // 나와 똑같은 크기가 나오면 탈출(그 전은 정렬을 했기 때문에 작음이 보장된다.)
        while (idx < vs && v[i].Size == v[idx].Size)
        {
            ++idx;
        }
 
        // 자신과 같은 크기들에 대한 답을 저장한다.
        for (int j = i; j < idx; j++) {
            ans[v[j].Index] = total - sum[v[j].Color];
        }
 
        // 자신과 같은 크기들에 대한 Size의 합(total)
        // 그리고 자신과 같은 색깔에 대한 Size의 합(sum[])
        for (int j = i; j < idx; j++) {
            total += v[j].Size;
            sum[v[j].Color] += v[j].Size;
        }
 
        i = idx - 1;
    }
 
    for (int i = 0; i < n; i++) {
        printf("%d\n", ans[i]);
    }
 
    return 0;
}