[백준/BOJ]18881번 Social Distancing II

<문제>

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

18881번: Social Distancing II

 

 

문제 해설을 하자면,

 

소들의 수인 N(1<=N<=1000)이 들어 오고 그후 N개 만큼 소의 위치x 와 감염여부를 상태인 s가 들어온다.

(소들은 일직선 위에 있다.)

 

구해야하는 것은 감염이 시작되기전 최초의 감염된 소의 수가 최소가되는 소의 수를 구하라이다.

 

 

 

풀이는

 

그렇게 어렵지 않았는데, 결과의 감염여부가 0인 소가 감염된 소인 1과 맞닿아있는 부분이 중요하다는 점이다.

 

해당부분에서 감염 범위인 R을 구할 수 있기 때문에 이부분을 탐색하며, 0과 1이 맞닿은 부분의 거리들의 최소값을 구하고 그 값에서 -1을 한것이 최대 R이다.

 

그후 구한 R을 이용하여 감염된 소들을 돌며 거리차가 R보다 크다면 다른 그룹이라고 인식해 그룹별로 최초 전파자가 1마리씩 있다고 이해하면 금방 풀 수 있다.

 

 

 

<정답 코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<math.h>
#include<stack>
#include<map>
#include<string.h>
#include<cmath>
#include<deque>
using namespace std;

typedef long long ll;

int main(void) {
	int N;
	cin >> N;
	vector<pair<int, int>>cow;
	vector<int>cand;
	for (int i = 0; i < N; i++) {
		int x, s;
		cin >> x >> s;
		cow.push_back({ x,s });
	}
	sort(cow.begin(), cow.end());
	int R = 1e9;
	for (int i = 0; i < cow.size(); i++) {
		if (cow[i].second == 0) {
			if (i - 1 > 0&&cow[i-1].second==1) {
				R = min(R, cow[i].first - cow[i - 1].first);
			}
			if (i + 1 < cow.size()&&cow[i+1].second==1) {
				R = min(R, cow[i + 1].first - cow[i].first);
			}
		}
		if (cow[i].second == 1)cand.push_back(cow[i].first);
	}
	R--;
	int re = 0;
	for (int i = 0; i <cand.size()-1; i++) {
		if (cand[i + 1] - cand[i] > R)re++;
	}
	printf("%d\n", re+1);



	return 0;
}