[백준 1781] 컵라면

문제

백준 1781

유형

• 그리디
• 유니온 파인드

풀이

백준 10775번 문제와 거의 똑같은 문제였다. 이전에 풀어봤던 유형이지만 같은 풀이로 풀 수 있는 문제라고 바로 알아채지는 못했다. 조금 더 이런 유형의 문제풀이에 익숙해져야할 것 같다.

먼저 컵라면 수를 기준으로 내림차순으로 정렬하고 각 유니온 파인드를 사용하기 위해 parent배열을 만든다 여기서 이 배열값의 의미는 각 인덱스 이하에 몇개의 빈 공간이 있는지이다.

그럼 컵라면 수가 큰 문제부터 차례대로 쌓아넣고 들어갈 공간이 있으면 정답에 카운트하는 방법으로 풀이하였다.

코드

#include <bits/stdc++.h>
using namespace std;

int n;
pair<int, int> v[200001];
int parent[200001];

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

void merge(int x, int y) {
	x = Find(x);
	y = Find(y);
	parent[x] = y;
}

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	
	cin >> n;
	long long ans = 0;
	for (int i = 1; i <= n; i++) parent[i] = i;
	for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;

	sort(v, v + n, cmp);

	for (int i = 0; i < n; i++) {
		int c = Find(v[i].first);
		if (c != 0) ans += v[i].second;
		merge(c, c - 1);
	}

	cout << ans;

	return 0;
}