[BOJ] 10800 컬러볼

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

10800번: 컬러볼

문제

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

공 번호                                               색                                                        크기

1	1	10
2	3	15
3	1	3
4	4	8

이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면, 1번 공은 크기가 더 큰 2번 공과 색이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다. 

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

 

입력

첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다.

출력

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

---

구상

공을 크기 순으로 정렬한 후, 작은 공부터 크기의 총합(total)을 구한다.

이때 각 공의 색깔별로 크기의 총합을 따로 구해 dp라는 배열에 저장한다.

임의의 n번째 공이 잡을 수 있는 공 크기의 총합은 (total - dp[n])이 된다.

 

단, 이때 크기가 같은 경우 total을 구하는 데 무리가 있으므로 크기가 같은 경우에는 unordered_map을 이용해 임시 메모리에 저장했다가 dp와 total에 변경한 값을 적용한다.

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

using namespace std;

bool cmp(vector<int> a, vector<int> b){
    return a[2] < b[2];
}
int main(){
    int n;
    vector < vector<int> > arr; // vector {number, color, size}
    cin >> n;
    int dp[200001] = {0,};
    int ans[n] = {0,};
    int tot = 0;
    for(int i = 0; i < n; i++){
        int color, size;
        cin >> color >> size;
        vector<int> v = { i, color, size};
        arr.push_back(v);
    }
    sort(arr.begin(),arr.end(),cmp);
    int cur_size = -1;
    int accum_size = 0;
    vector< vector<int> > v;
    for(int i = 0; i < arr.size(); i++){
        unordered_map<int, int> cache;
        if(cur_size == arr[i][2]){
            if(accum_size == 0){
                accum_size += cur_size;
                tot -= cur_size;
            }
            ans[arr[i][0]] = tot - dp[arr[i][1]];
            accum_size += arr[i][2];
            
            unordered_map<int, int>::iterator finder = cache.find(arr[i][1]);
            if( finder != cache.end() ) finder->second = finder->second + arr[i][2];
            else cache.insert(unordered_map<int, float>::value_type(arr[i][1],arr[i][2]));
        }
        else{
            unordered_map<int, int>::iterator iter;
            for( iter = cache.begin(); iter != cache.end(); iter++ ){
                dp[iter->first] += iter->second;
            }
            cache.clear();
            ans[arr[i][0]] = tot - dp[arr[i][1]];
            tot += (accum_size + arr[i][2]);
            accum_size = 0;
            cur_size = arr[i][2];
            dp[arr[i][1]] += arr[i][2];
        }
    }
    for(int i = 0; i < n; i++) cout << ans[i] << endl;
    return 0;
}

map의 접근속도가 느리지 않아서 속도가 오래걸리지 않을것이라 생각했는데 시간초과가 발생했다.

 

 

--해결--

iostream의 std::cin과 std::cout을 printf scanf로 바꾸었더니 통과한다 ㅜㅜ

귀찮아서 iostream을 쓰고 있었는데 정말 골때리는 결과... 앞으로는 stdio쓰기로!

#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

bool cmp(vector<int> a, vector<int> b){
    if (a[2] == b[2]) return a[1] < b[1];
    return a[2] < b[2];
}
int same_color[200001], same_size[200001], sum[200001];

int main(){
    int N;
    scanf("%d",&N);
    vector< vector<int> > balls;
    for (int i = 0; i < N; i++){
        int color; int size;
        scanf("%d%d",&color,&size);
        vector<int> this_ball = {i, color, size};
        balls.push_back(this_ball);
    }
    sort(balls.begin(), balls.end(), cmp);
	
    int sum_all = 0;
    for (int i = 0; i < N; i++){
        int idx = balls[i][0];
        int c = balls[i][1];
        int s = balls[i][2];
		
        sum_all += s;
        same_color[c] += s;
        same_size[s] += s;
		
        sum[idx] = sum_all + s - same_color[c] - same_size[s];
        
        if(i!=0) if(balls[i-1][1] == c && balls[i-1][2] == s) sum[idx] = sum[balls[i-1][0]];
    }
    for (int i = 0; i < N; i++)
        printf("%d\n",sum[i]);
}