💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 상어의 마리 수 N이 주어진다. 이 값은 50보다 작거나 같은 자연수이다. 둘째 줄부터 각 상어의 크기, 속도, 지능의 정보가 주어진다. 이 값은 2,000,000,000보다 작거나 같은 자연수이다.

🧺출력
첫째 줄에 살아남을 수 있는 상어 수의 최솟값을 출력한다.

🔋예제 입출력

🔮예제 입력

5
4 5 5
10 10 8
5 7 10
8 7 7
8 10 3

🔮예제 출력

2

💉문제 분석

🔋분류

네트워크유량, 최대유량, 이분매칭

🔋난이도

플래티넘III

💉문제 풀이

🔋해법

일반 이분매칭문제이지만, 주의해야할요소는 네가지입니다.

1. "한 상어가 최대 두 개의 상어만 먹을 수 있게 했다."
   > 이분매칭을 총 두번 실행한다.
2. "상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다."
   > 그래프상으로 크기, 속도, 지능이 큰것이 작은것을 가리킨다.
3. "능력치가 모두 같은 상어 A, B가 있다면 A가 B를, B가 A를 잡아먹을 수는 있지만 A, B가 서로 잡아먹을수는 없다."
   > 능력치가 같은 상어는 그래프상으로 누가 누구를 가리키든 상관없다.
4. "살아남을 수 있는 상어 수"
   > 살아남을 수 있는 상어 수 = (상어의 전체수) - (죽은 상어수 또는, 잡아먹힌 상어수)

자.. 그러면, 위 내용을 참고하여 만들자면은 제일 중요한부분은 입력부분입니다.
각 상어의 능력치를 저장하는 배열을 만들어놓고, 이후에 2중 반복문으로 각 상어의 능력치에 알맞게 서로를 가리키도록 만들었습니다.

능력치가 같은 상어는 누가 누굴 가리키든 상관없으므로 크게 고려하지 않았습니다.
상어의 능력치에 대한 값비교는 연산자오버로딩을 썼습니다.

결과값은 살아남을 수 있는 상어 수 입니다.
이분매칭으로 얻을 수 있는 정보는 잡아먹힌 상어수와 어떤 상어가 어떤 상어를 잡아먹었는지만 알수있습니다.
따라서 잡아먹힌 상어수가 A라 하고 전체 상어수가 N이라 한다면, 답은

답 = N - A

가 되겠습니다.

🔋소스코드

#include <bits/stdc++.h>

//Static variables
constexpr int MAX = 51;
constexpr int INF = 987654321;

struct Shark {
	int it, sz, vc;
	bool operator==(Shark shrk) {
		return ((it == shrk.it) && (sz == shrk.sz) && (vc == shrk.vc));
	}
	bool operator<=(Shark shrk) {
		return ((it <= shrk.it) && (sz <= shrk.sz) && (vc <= shrk.vc));
	}
	bool operator>=(Shark shrk) {
		return ((it >= shrk.it) && (sz >= shrk.sz) && (vc >= shrk.vc));
	}
};

//AlgoCapsule
class AlgoCapsule {
public:
	void Run() {
		Input();
		Solve();
		Output();
	}

	void Input() {
		std::cin >> N;

		for (int i = 1; i <= N; ++i) {
			int it, sz, vc;
			std::cin >> shrk[i].sz >> shrk[i].vc >> shrk[i].it;
		}

		for (int i = 1; i <= N - 1; ++i) {
			for (int j = i + 1; j <= N; ++j) {
				if (shrk[i] >= shrk[j]) {
					adj[i].push_back(j);
				}
				else if (shrk[i] <= shrk[j]) {
					adj[j].push_back(i);
				}
			}
		}
	}

	void Solve() {
		for (int k = 0; k < 2; ++k) {
			for (int i = 1; i <= N; i++) {
				std::fill(visit, visit + MAX, false);
				if (BipartiteMatching(i)) count++;
			}
		}
	}

	void Output() {
		std::cout << N - count;
	}

	bool BipartiteMatching(int start) {
		for (int i = 0; i < adj[start].size(); ++i) {
			int x = adj[start][i];

			if (visit[x]) continue;
			visit[x] = true;

			if (d[x] == 0 || BipartiteMatching(d[x])) {
				d[x] = start;
				return true;
			}
		}
		return false;
	}

	AlgoCapsule() { }
private:
	Shark shrk[MAX];
	bool visit[MAX];
	int d[MAX];
	std::vector<int> adj[MAX];
	int N, count = 0;
};

//Module Entry
int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	AlgoCapsule AC;
	AC.Run();

	return 0;
}

난이도에 비해서 비교적 쉬운문제였습니다.
확실히 이분매칭도 따지고보면 네트워크유량에 들어가는 문제라서 재밌고, 네트워크유량과 같이 저한테 잘 맞는 유형의 문제들인것같습니다.

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~