6209 : 제자리 멀리뛰기

풀이

이분탐색을 해주자

mid를 최소로 뛰는 거리로 두고 파라메트릭 해주자.

코드

#include <cstdio>
#include <algorithm>
using namespace std;

int d, n, m, a[50005];

int main() {
	scanf("%d %d %d", &d, &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	a[n + 1] = d;

	sort(a + 1, a + n + 1);

	int lft = 0, rgt = d, ans;
	while (lft <= rgt) {
		int mid = (lft + rgt) / 2;
		int pos = 0, cnt = 0;
		for (int i = 1; i <= n + 1; i++) {
			if (a[i] - a[pos] < mid) cnt++;
			else pos = i;
		}
		if (cnt > m) rgt = mid - 1;
		else lft = mid + 1, ans = mid;
	}

	printf("%d", ans);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-03-30 10:03

Read more posts by this author