백준 2110 : 공유기 설치
https://www.acmicpc.net/problem/2110
1. 접근
- 거리의 범위는 1~(처음집과 끝집의 거리) 이다.
- 빠르게 정답 거리를 찾아내기 위해 이진탐색을 사용한다.
- 첫 집을 고정시켰을 때 대부분의 경우 답을 찾아낼 수 있다.
(참고 : https://www.acmicpc.net/board/view/50802) - 첫 집과 i번째 집과의 거리가 mid와 일치하면, i번째 집과 그 다음 집과의 거리로 넘어간다
2. 나의 풀이
#include <iostream>
#include <algorithm>
#define MAX 200001
using namespace std;
int main() {
int n, c;
cin >> n >> c;
int house[MAX];
for (int i = 0; i < n; i++) {
cin >> house[i];
}
sort(house, house + n);
int start=1, end=(house[n-1]-house[0]), mid;
int ret = 0; //최소거리의 최댓값
while (start <= end) {
mid = (start + end) / 2;
int prev = house[0];
int tem = 1;
for (int i = 1; i < n; i++) {
if (house[i] - prev >= mid) {
tem++;
prev = house[i];
}
}
if (tem >= c) {
ret = max(ret, mid);
start = mid + 1;
}
else end = mid - 1;
}
cout << ret << "\n";
return 0;
}
3. 참고
https://mygumi.tistory.com/301
http://melonicedlatte.com/algorithm/2018/07/29/132129.html
Author And Source
이 문제에 관하여(백준 2110 : 공유기 설치), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeongopo/백준-2110-공유기-설치저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)