문제
https://www.acmicpc.net/problem/2110
Algorithm
임의의 두 공유기 사이의 거리를 늘리게 되면, 이외의 공유기와의 거리가 가까워질 수 있으므로 최대한 평등하게 설치하는 것이 핵심 아이디어다.
이분탐색을 진행하여, 가장 왼쪽부터 시작해 공유기를 설치한 집으로부터 임의의 수 k이상 떨어진 집에 설치하는 것을 반복한다.
더 이상 설치할 수 없는 경우, 설치한 공유기의 개수가 c개 이상이라면 k를 줄인 후 재설치한다.
c개 미만이라면, k를 키워 재설치한다.
이분탐색이 끝난 후의 k가 출력 답안이 된다.
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,c;
vector<int> home;
void INPUT()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> c;
for(int i = 0; i < n; i++)
{
int x; cin >> x;
home.push_back(x);
}
}
void SOLVE()
{
sort(home.begin(),home.end());
int left = 1, right = home[n-1];
int ans;
while(left <= right)
{
int mid = (left + right) / 2;
int setIdx = home[0];//가장 마지막에 설치한 집의 위치
int cnt = 1;//가장 왼쪽 집에는 무조건 설치
for(int i = 1; i < n; i++)
{
//공유기로부터 mid 이상 떨어져있다면 설치
if(setIdx + mid <= home[i])
{
setIdx = home[i];
cnt++;
}
}
if(cnt < c) right = mid - 1;
else ans = mid , left = mid + 1;
}
cout << ans;
}
int main()
{
INPUT();
SOLVE();
}
'Koala - 9기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/Java] 2805 나무 자르기 (0) | 2023.01.29 |
---|---|
[백준/python] 10816번 숫자 카드 2 (0) | 2023.01.29 |
[백준/Python] 11663 선분위의 점 (0) | 2023.01.26 |
[백준 / Python] 15038번 Lounge Lizards (0) | 2023.01.25 |
[백준/c++] 3027번 입국심사 (Binary Search) (0) | 2023.01.25 |