[BOJ] 2109 순회공연

https://www.acmicpc.net/status?user_id=yhkim8917&problem_id=2109&from_mine=1 

채점 현황

옛날에 무작정 그리디로 풀었는데 엄청 틀리고 반례는 알게 되었지만 해결하지 못한 문제이다.

저번 학기에 알고리즘 설계와 분석 시간에 해당 문제를 배워서 수월하게 풀 수 있었다.

알설분 시간에는 disjoint set을 구현하여 풀었지만 해당 문제는 d의 값이 최대 10000밖에 되지 않기 때문에 그냥 크기 10000짜리 배열을 선언하여 풀었다.

 

일단 p와 d값 벡터에 저장 후에 벡터를 p를 기준으로 내림차순 정렬을 한다. 그리고 벡터를 반복문을 돌면서 벡터의 d값에 최대한 가까운 j번째에 p값을 저장해주면 된다.

 

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long[

using namespace std;

vector<pair<int,int> > v;
int n,p,d;
int d_[10001];

bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first > b.first;
}

void input() {
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>p>>d;
        v.push_back(make_pair(p,d));
    }
}

void init() {
    sort(v.begin(),v.end(),cmp);
}


int solution() {
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=v[i].second;j>0;j--){
            if(d_[j]==0){
                d_[j]=v[i].first;
                break;
            }
        }
    }
    
    for(int i=0;i<=10000;i++) ans+=d_[i];
    return ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    init();
    cout<<solution();
    return 0;
}