글 읽기 - 어떤 반례가 있을까요??

qkrclrl701 5년 전 0

최대 유량 알고리즘은 아직 공부를 안해서 그냥 제 생각대로 풀었는데요,

자신을 잡아먹는 상어가 많은 순으로 상어들을 정렬하고, 그 순서대로 각 상어들이 greedy하게 최대한 많은 상어를 먹도록 구현하였는데요

만약에 상어 A를 잡아먹는 상어의 수가 상어 B를 잡아먹는 상어의 수보다 크면,

상어 A가 먼저 자신보다 약한 상어들을 다 잡아먹어 버리니, 상어 A가 다른 상어들을 잡아먹기 전에 B가 A를 잡아먹어 버리는 경우가 없어져서 최적의 해를 구할 수 있을거라고 생각했는데요, 어떠한 경우에 최적의 해를 구하지 못하는 것일까요??

#include <stdio.h>
#include <algorithm>
using namespace std;
pair<int, pair<int, pair<int, int> > > a[51];
int c[51];

int cmp_shark(pair<int, pair<int, pair<int, int> > > a, pair<int, pair<int, pair<int, int> > > b){
	return c[a.first] >= c[b.first];
}
int main(){
	int N, i, j;
	scanf("%d", &N);
	for(i = 0; i < N; i++){
		scanf("%d %d %d", &a[i].second.first, &a[i].second.second.first, &a[i].second.second.second);
		a[i].first = i;
	}
	for(i = 0; i < N; i++){
		for(j = 0; j < N; j++){
			if(i == j){
				continue;
			}
			if(a[i].second.first <= a[j].second.first &&
			a[i].second.second.first <= a[j].second.second.first &&
			a[i].second.second.second <= a[j].second.second.second){
				c[i]++;
			}
		}
	}
	sort(a, a + N, cmp_shark);
	for(i = 0; i < N; i++){
		int cnt = 0;
		for(j = 0; j < i; j++){
			if(cnt == 2){
				break;
			}
			if(a[j].first != -1 && a[i].second.first >= a[j].second.first &&
			a[i].second.second.first >= a[j].second.second.first &&
			a[i].second.second.second >= a[j].second.second.second){
				cnt++;
				a[j].first = -1;
			}
		}
	}
	int num = 0;
	for(i = 0; i < N; i++){
			if(a[i].first != -1){
			num++;
		}
	}
	printf("%d", num);
}

qkrclrl701 5년 전 1

반례가 생각이 났습니다.

상어 4가 0 1 2 3 을 잡아먹을 수 있고,

상어 5가 0를 잡아먹을 수 있는 상황을 가정하면

상어 4가 0, 1을 먼저 잡아먹어 버리므로 상어 5가 0을 못잡아 먹어서 낭비가 일어나게 되네요.

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

문제

문제

출처

ICPC

어떤 반례가 있을까요??

qkrclrl701 5년 전 0

qkrclrl701 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말