[백준/BOJ] 18877번 Social Distancing

오늘 많네....

 

처음에 문제를 잘못 이해해서 꽤나 틀린 문제이다..

 

영어를 대충 읽은 탓이좀....한끝 차이로...ㅜㅜ

 

 

<문제>

 

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

18877번: Social Distancing

 

문제 해석을 하자면,

N은 소의 마리, M은 잔디 범위의 갯수이다. 잔디는 범위가 겹치거나 끝점이 같은 경우는 없다고 한다.

 

문제는 소는 잔디 범위위에만 있을 수 있으며, 소들사이의 각각의 거리가 D이상인 D의 최대값을 구하는 문제이다.

 

 

 

풀이는

D의 값을 이분 탐색으로 최대값으로 찾을수있는데, 범위가 10^18까지라 너무커서 여기서 이분탐색을 생각해냈다.

 

소들을 최대한 많이 넣어 들어간 소들의 수를 기준으로 L과 R을 잡았다.

 

범위들을 정렬하고 현재 위치에서 D의 거리만큼 뒤에 소를 넣어보면서 잔디 범위안이면 넣고

 

넘어가서 다음 범위 안이면 넣고, 범위가 아니면 그 다음 잔디 범위의 시작점에 소를 넣는다.

 

수가 크기 때문에 long long 자료형을 사용했다.

 

 

 

<정답 코드>

#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 N, M;
vector<pair<ll, ll>>gap;
int getnum(ll d) {
	int cnt = 1;
	int pre = gap[0].first;
	for (int i = 0; i < M; i++) {
		ll s = gap[i].first;
		ll e = gap[i].second;
		while (pre+d<=e) {
			pre = max(pre + d, s);
			cnt++;
		}
	}
	return cnt;
}
int main(void) {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		ll s, e;
		cin >> s >> e;
		if (s > e)swap(s, e);
		gap.push_back({ s,e });
	}
	sort(gap.begin(), gap.end());
	ll L = 1, R = 1e18;
	ll re = 0;
	while (L <= R) {
		ll mid = (L + R) / 2;
		ll pre = getnum(mid);
		if (pre >= N) {
			L = mid + 1;
			re = mid;
		}
		else {
			R = mid - 1;
		}

	}
	printf("%lld\n", re);
	return 0;
}