[백준 2617] 구슬 찾기

홍시홍 2020. 3. 5. 21:49

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

2617번: 구슬 찾기

모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아 래와 같은 일을 하려 한다. 우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운 가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운 가를 모

www.acmicpc.net

요구사항

1. 중간 값이 될 수 없는 수의 개수 찾기

풀이

중간 값이 될 수 없다 == 현재 구슬보다 무겁거나or가벼운것이 (n+1)/2 보다 많을때

dfs로 현재 구슬보다 무거운 구슬이 몇개 인지 구한다

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;
#define Input(n,m) scanf("%d%d",&n,&m);
#define For(i ,x, n) for(int i=x ; i < n ; i++)

int n, m;
vector<int> vmax[100];
vector<int> vmin[100];
int visit[100];
int maxnum[100];
int minnum[100];

void maxdfs(int now,int start) {
	visit[now] = 1;
	maxnum[start]++;
	for (int i = 0; i < vmax[now].size(); i++) {
		int next = vmax[now].at(i);
		if (visit[next] == 0)
			maxdfs(next,start);
	}
}

void mindfs(int now, int start) {
	visit[now] = 1;
	minnum[start]++;
	for (int i = 0; i < vmin[now].size(); i++) {
		int next = vmin[now].at(i);
		if (visit[next] == 0)
			mindfs(next, start);
	}
}

int main(){
	Input(n, m);
	For( i, 0, m){
		int x, y;
		Input(x, y);
		vmax[x].push_back(y);
		vmin[y].push_back(x);
	}
	For(i,1,n+1) {
		memset(visit, 0, sizeof(visit));
		maxdfs(i,i);
	}
	For(i, 1, n + 1) {
		memset(visit, 0, sizeof(visit));
		mindfs(i, i);
	}
	int criteria = (n+1) / 2;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (maxnum[i] > criteria)
			ans++;
		if (minnum[i] > criteria)
			ans++;
	}
	cout << ans << endl;

}