[백준 10800] 컬러볼 [C]

백준 - 10800

 

---

풀이

i번째 공이 잡을 수 있는 크기는 i번째 공보다 크기가 작고, 색상이 다른 공들의 합이기 때문에, 입력받은 공들을 공의 크기, 색별로 정렬을 해주었다.

 

출력순서는 입력순서와 동일해야 하므로, 정렬된 정보들에 대해 index별로 담아 줄 수 있는 배열들을 사용했다.

for (int i = 0; i < N; i++){
    scanf("%d %d", &b[i].color, &b[i].size);
    b[i].idx = i;
}
qsort(b, N, sizeof(Ball), compare);
	
int sum_all = 0;
for (int i = 0; i < N; i++){
    int s = b[i].size, c = b[i].color, idx = b[i].idx;
		
    sum_all += s;
    same_color[c] += s;
    same_size[s] += s;

 

그리고 위에서 언급한대로 다음과 같이 계산하면 정답을 구할 수 있다.

단, 누적 합 방식이다 보니 이전의 공과 색갈이 같고, 크기가 같은 경우는 예외로 해줘야 한다.

    sum[idx] = sum_all + s - same_color[c] - same_size[s];
    if (i){
        if (b[i-1].color == c && b[i-1].size == s)
            sum[idx] = sum[b[i-1].idx];
    }
}

---

소스코드

#include <stdio.h>
#include <stdlib.h>
#define MAX 200001
typedef struct{
    int idx, color, size;
}Ball;

int same_color[MAX], same_size[MAX], sum[MAX];

int compare(const void *a, const void *b){
    Ball *n1 = (Ball*)a, *n2 = (Ball*)b;
    if (n1->size == n2->size)
        return n1->color - n2->color;
    return n1->size - n2->size;
}
int main(){
    int N;
    scanf("%d", &N);
    Ball b[N];
    for (int i = 0; i < N; i++){
        scanf("%d %d", &b[i].color, &b[i].size);
        b[i].idx = i;
    }
    qsort(b, N, sizeof(Ball), compare);
	
    int sum_all = 0;
    for (int i = 0; i < N; i++){
        int s = b[i].size, c = b[i].color, idx = b[i].idx;
		
        sum_all += s;
        same_color[c] += s;
        same_size[s] += s;
		
        sum[idx] = sum_all + s - same_color[c] - same_size[s];
        if (i){
            if (b[i-1].color == c && b[i-1].size == s)
                sum[idx] = sum[b[i-1].idx];
        }
    }
    for (int i = 0; i < N; i++)
        printf("%d\n", sum[i]);
}

---

출처

10800번: 컬러볼