Baekjoon 10800번 컬러볼

문제

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

걸린 시간

01 : 44 : 24 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int n, c, s;
int result[200000];
int total[200001], tmp[200001];
vector<tuple<int, int, int>> ball; // size, color, num

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> c >> s;
        ball.push_back(make_tuple(s, c, i));
    }
    sort(ball.begin(), ball.end());
    memset(total, 0, sizeof(total));
    memset(tmp, 0, sizeof(tmp));
    int last = 0;
    for(int i = 0; i < n; i++){
        int size = get<0>(ball[i]);
        int color = get<1>(ball[i]);
        int num = get<2>(ball[i]);
        // size 가 달라지면 total 갱신
        if(last != size)
            for(int j = 1; j <= n+1; j++)
                total[j] = tmp[j];
        result[num] = total[n+1] - total[color];
        // tmp 갱신
        tmp[color] += size;
        tmp[n+1] += size;
        // size 갱신
        last = size;
    }
    for(int i = 1; i <= n; i++)
        cout << result[i] << "\n";
    return 0;
}

1. 크기, 색깔별로 누적한 크기값을 2차원 배열에 저장 : 메모리 초과
2. map 에 크기, 색깔 쌍을 키값으로 누적값을 저장 : 시간 초과

크기를 기준으로 오름차순 정렬한 뒤, 현재 크기의 공이 사로잡을 수 있는 모든 공들의 크기 합을 1차원 배열에 갱신해나가며 정답을 계산해야 메모리, 시간 초과 없이 통과할 수 있다.

효율적인 풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int n, c, s;
int result[200000], total[200001];
vector<tuple<int, int, int>> ball; // size, color, num

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> c >> s;
        ball.push_back(make_tuple(s, c, i));
    }
    sort(ball.begin(), ball.end());
    memset(total, 0, sizeof(total));
    int j = 0;
    for(int i = 0; i < n; i++){
        while(get<0>(ball[j]) < get<0>(ball[i])){
            total[get<1>(ball[j])] += get<0>(ball[j]);
            total[n+1] += get<0>(ball[j]);
            j++;
        }
        result[get<2>(ball[i])] = total[n+1] - total[get<1>(ball[i])];
    }
    for(int i = 1; i <= n; i++)
        cout << result[i] << "\n";
    return 0;
}

size 가 달라질 때 마다 n 크기의 배열을 전부 복사하며 갱신하던 작업을 최적화함.

O(sn) -> O(n) // s : size, n : num