미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!
https://www.acmicpc.net/problem/2110
공유기
문제
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
풀이
주어진 범위가 10억. 이렇게 큰 수의 범위에서는 이분탐색의 응용인 parametric search를 이용해볼 생각을 먼저 하는 것이 좋다.
우선, 공유기를 항상 첫 집에 하나 설치해준다고 하자.
우리가 구하고자 하는 것은 가장 가깝게 설치된 공유기 사이의 거리가 최대가 되는 값이다.
그 값을 d라고 한다면, 공유기는 항상 d보다 크거나 같은 간격으로 설치되어야 한다.
이 d값을 parametric search로 찾아내는 것이 핵심이다.
그렇다면 값이 변하는 기준을 정해주자.
집i의 위치를 house[i]라고 하자.
그러면, 그 집과 그 이전에 공유기를 설치한 집 사이의 간격은 house[i] - before_house 가 된다.
이 값이 mid보다 크거나 같은지를 비교하여 그 집에 공유기를 설치해도 되는지를 판단, 공유기를 설치한다.
그 후 설치된 공유기 수와 공유기의 수 C 둘을 비교해 탐색을 진행한다.
#include <iostream>
#include <algorithm>
using namespace std;
int house[200001];
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int N, C;
cin >> N >> C;
int h;
for (int i = 0; i < N; i++) {
cin >> h;
house[i] = h;
}
sort(house, house + N);
int left = 0;
int right = house[N - 1];
int mid = (left + right) / 2;
int answer = 0;
while (left <= right) {
int h = house[0];
int count = 1;
for (int i = 1; i < N; i++) {
if (house[i] - h >= mid) {
count++;
h = house[i];
}
}
if (count >= C) {
left = mid + 1;
answer = max(answer, mid);
}
else {
right = mid - 1;
}
mid = (left + right) / 2;
}
cout << answer << endl;
return 0;
}
'코딩 테스트(Coding test) > BOJ' 카테고리의 다른 글
[BOJ 2805번/C++] 나무 자르기 (0) | 2022.11.02 |
---|---|
[BOJ 2630번/C++] 색종이 만들기 (0) | 2022.11.02 |
[BOJ 2580번/C++] 스도쿠 (0) | 2022.10.18 |
[BOJ 2178번/C++] 미로 탐색 (1) | 2022.10.15 |
[BOJ 1654번/C++] 랜선 자르기 (1) | 2022.10.13 |