글 읽기 - 반례를 도저히 못찾겠습니다.

kja9294 3년 전 0

제 머리로는 도저히 반례를 못찾겠습니다..ㅜㅜ

같은 능력치 상어일 경우 인덱스 순으로 우선순위를 줘서 간선을 연결해 줬습니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
int N;

struct jaws {
	ll a, b, c;
	int sizes; //먹을 수 있는 상어 방문 횟수
	jaws() {
		sizes = 0;
	}
};
bool operator <(jaws A, jaws B) {
	if(A.a!=B.a)return A.a < B.a;
	if (A.b != B.b)return A.b < B.b;
	return A.c < B.c;
}

vector<jaws> vt; //상어정보
vector<vector<int>> child; //각 상어의 간선 저장
vector<int> check; //해당 상어를 먹었는지 체크

bool dfs(int n) {
	int num;
	while(vt[n].sizes < child[n].size()) {// 아직 다 방문 안한 경우
		num = child[n][vt[n].sizes++];
		if (check[num] == -1) {
			check[num] = n; //n번 상어가 방문했음 체크
			return true;
		}
		else if (dfs(check[num])) {
			check[num] = n;
			return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio;
	cin.tie(0);
	cin >> N;
	vt.resize(N);
	child.resize(N);
	check.resize(N, -1);
	for (int i = 0; i < N; i++) cin >> vt[i].a >> vt[i].b >> vt[i].c;
	sort(vt.begin(), vt.end()); //정렬 후 해당 상어 인덱스 보다 낮은 상어 매칭
	for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) {
		if (vt[j].a <= vt[i].a&&vt[j].b <= vt[i].b&&vt[j].c <= vt[i].c) child[i].push_back(j);
	}
	int answer = N;
	for (int i = 0; i < N; i++) {
		if (dfs(i))answer--;
		if (dfs(i))answer--;
	}
	cout << answer << endl;
}
	

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 도저히 못찾겠습니다.

kja9294 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말