[백준BOJ] 1671 상어의 저녁식사

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

1671번: 상어의 저녁식사

---

문제해설

밑의 문제와 비슷한 유형의 문제입니다. 

단, 문제 조건을 잘 읽고 따져야 되는 문제입니다.

 

2019/10/13 - [알고리즘/BOJ] - [백준BOJ] 11376 열혈강호2

[백준BOJ] 11376 열혈강호2

 

우선 문제에서 제시한 조건에 의해서 내림차순으로 정렬을 해줍니다.

정렬된 vector 에서 i < j 라고 할떄

• vec[i] 는 vec[j] 를 잡아먹을 수 있고( 단 , 속도, 지능, 크기가 모두 크거나 같야아 합니다 )
• vec[j] 는 vec[i] 를 어떠한 경우에도 잡아 먹을 수 없습니다.

조건에 만족하는 경우 i 에서 j 에서 가능 경로가 있다고 생각하고 ( 간선의 가중치 1 )

한 상어당 2번의 flow를 발생시키면 됩니다.

 

 

---

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------

#define MAX_N 51
class Shark {
public:
	int size, speed, intel;
	Shark(int size, int speed, int intel) {
		this->size = size; this->speed = speed; this->intel = intel;
	}
	bool operator < (const Shark  & b) const {
		if (this->size == b.size && this->speed == b.speed) {
			return this->intel > b.intel;
		}if (this->size == b.size) {
			return this->speed > b.speed;
		}
		else {
			return this->size > b.size;
		}
	}

	bool operator >= (const Shark  & b) const {
		if (this->size >= b.size && this->speed >= b.speed && this->intel >= b.intel) {
			return true;
		}
		else {
			return false;
		}
	}
}; vector<Shark> shark;

int eat[MAX_N];
int eated[MAX_N];
bool visit[MAX_N];
int N;

bool fun(int n) {
	visit[n] = true;
	for (int i = n + 1; i < N; i++) {
		if (shark[n] >= shark[i]) {
			if (eated[i] == -1 || (!visit[eated[i]] && fun(eated[i]))) {
				eat[n] = i;
				eated[i] = n;
				return true;
			}
		}
	}
	return false;
}


int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b, c; cin >> a >> b >> c;
		shark.push_back(Shark(a, b, c));
	}
	sort(shark.begin(), shark.end());
	//cout << "정렬 후" << endl;
	//for (const auto &x : shark)
	//	cout << x.size << "  " << x.speed << " " << x.intel << endl;
	int ans = N;
	memset(eat, -1, sizeof(eat));
	memset(eated, -1, sizeof(eated));

	for (int i = 0; i < N; i++) {
		if (eat[i] == -1) {
			memset(visit, false, sizeof(visit));
			if (fun(i)) ans--;
			if (fun(i)) ans--;
		}
	}
	cout << ans << endl;
}

---

기타