백준 2110 공유기 설치
문제
풀이
공유기 사이의 "간격"을 이분 탐색으로 찾는다.
예를 들어 간격이 3이라면 첫 번째 집에 공유기를 설치하고, 두 번째 집부터 돌면서 이전 공유기와의 간격이 3이상인지 확인한다. 간격이 3 이상이라면 그 집에 공유기를 설치하고 다음 집을 탐색하며 간격 계산을 반복한다.
모든 집을 확인했을 때 설치된 공유기가 c보다 많으면 간격을 늘리고(right = gap - 1
), c보다 작거나 같으면 간격을 줄인다(left = gap + 1
)
소스코드
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, c;
cin >> n >> c;
vector<int> vec(n);
for (int i = 0; i < n; i++) {
cin >> vec[i];
}
sort(vec.begin(), vec.end());
int left = 1;
int right = vec[n - 1] - vec[0];
int ans = 0;
while (left <= right) {
int gap = (left + right) / 2;
int cnt = 1;
int bef = vec[0];
for (int i = 1; i < n; i++) {
if (vec[i] - bef >= gap) {
cnt++;
bef = vec[i];
}
}
if (cnt >= c) {
ans = gap;
left = gap + 1;
} else {
right = gap - 1;
}
}
cout << ans;
return 0;
}
이분탐색 코드의 틀은 그냥 외워버리자
while (left <= right) {
int mid = (left + right) / 2;
// mid 값으로 계산했을 때 조건을 만족하는 경우가 얼마나 되는지 구한다.
// 이 값을 cnt라고 하고, 최종적으로 만족해야 하는 값은 c라면
if ( cnt >= c) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
Author And Source
이 문제에 관하여(백준 2110 공유기 설치), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@emily2307/백준-2110-공유기-설치저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)