[백준 2109] 순회강연

• 문제 : 2109 순회강연
• 유형 : 그리디, 유니온 파인드
• 풀이 : 다른 여러 그리디 문제들과 같이 강연으로 벌 수 있는 최대 비용을 먼저 가져가는 방식으로 풀이하였다.
  10775번 문제와 풀이가 동일
• 코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int parent[10001];
struct pos
{
	int d, p;
};

bool cmp(pos& a, pos& b) {
	if (a.p == b.p) return a.d < b.d;
	else return a.p > b.p;
}

int find(int x) {
	if (x == parent[x]) return x;
	else return parent[x] = find(parent[x]);
}

void update(int x, int y) {
	x = find(x);
	y = find(y);
	parent[x] = y;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);

	vector<pos> v;
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int d, p; cin >> p >> d;
		v.push_back({ d, p });
	}
	for (int i = 1; i <= 10000; i++) parent[i] = i;

	sort(v.begin(), v.end(), cmp);

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int remain = find(v[i].d);
		if (remain == 0) continue;
		ans += v[i].p;
		update(remain, remain - 1);

	}

	cout << ans;

	return 0;
}