백준 15459번 : Haybale Feast - Union&Find dis-joint set C++ 문제풀이

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

15459번: Haybale Feast

1. 문제설명

영어로 된 문제여서 구글 번역을 한번 돌리면 좀 더 쉽게 이해가 가능합니다.

Union & Find 알고리즘을 이용하여 문제를 해결했습니다.

 

N개의 Haybale을 spiceness에 대해 오름차순으로 정렬합니다.

spiceness가 작은 Haybale 부터 확인하면서 그 Haybale의 위 아래에 있는 Haybale 중

자신보다 spiceness가 작은 게 있으면 Union 해줍니다.

 

이 과정을 반복하다가

자신이 속한 집단의 flavor 값 합이 M 이상이 된다면

자신의 spiceness를 출력해주면 됩니다.

 

 

---

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
int n;
long long m;
long long unf[100001];

pair<int, int> arr[100001];

struct Haybale {
	int node, flavor, spicy;
	bool operator<(const Haybale& b)const {
		return spicy < b.spicy;
	}
};

int Find(int x) {
	if (unf[x] < 0) return x;
	return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a == b) return;

	if (unf[a] >= unf[b]) {
		unf[b] += unf[a];
		unf[a] = b;
	}
	else {
		unf[a] += unf[b];
		unf[b] = a;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	vector<Haybale> v;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		arr[i] = { a,b };
		v.push_back({ i,a,b });
	}

	for (int i = 1; i <= n; i++) {
		unf[i] = -arr[i].first;
	}


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

	for (int i = 0; i < v.size(); i++) {
		int node = v[i].node;

		if (node - 1 >= 1 && arr[node - 1].second <= arr[node].second) {
			Union(node - 1, node);
		}
		if (node + 1 <= n && arr[node].second >= arr[node + 1].second) {
			Union(node + 1, node);
		}

		if (-unf[Find(node)] >= m) {
			cout << arr[node].second;
			return 0;
		}
	}


	return 0;
}

m의 범위에 유의해야 메모리초과와 런타임에러를 방지할 수 있습니다.