-
부잣집 문제인듯
-
문제풀이
처음에 문제가 이해가 안 되었다. 하나의 공유기를 사용가능한 수평거리를 알려줘야 하는게 아닌가 생각했는데, 그게 필요없는 문제였다.
어쨋거나, N개의 집에 C개의 공유기를 설치하는데, 가장 인접한 두 공유기 사이의 거리를 최대로 해야 한다고 한다..
-
가장 인접한 공유기의 거리 d 를 하나 정하면, 모든 , 공유기 사이의 거리들은 d이상 이어야 한다.
- 일단 집의 좌표들이 주어지면 (집 사이의 최소 거리 MIN ) (집 사이의 최대 거리 MAX)를 구해야할 것 같다.
- 첫 번 째 집 ~ 마지막 집 거리 —> MAX 거리
- 집의 좌표를 받으며 두 집 사이의 거리를 계산해 가며 —> MIN 거리를 구할 수 있다.
- 공유기의 위치 : 첫 위치에 위치 시키고 —> 다음 공유기 위치는?
- 일단 집의 좌표들이 주어지면 (집 사이의 최소 거리 MIN ) (집 사이의 최대 거리 MAX)를 구해야할 것 같다.
-
라고 생각하니, 나무자르기 문제가 생각났다.(MAX, MIN이 있다고 생각하니..) 이것도 이분법 문제 같다.
-
n의 개수가 최대 20만개이기 때문에 O(n^2)만 되어도 40억이 되기에 시간초과의 위험이 생긴다. 이분탐색이 생각나는데 모르겠다
-
-
알고리즘
내가 풀지 못했다. 모르겠어서 다른 분의 풀이를 읽어보았다.- 나무 자르기 문제 처럼 풀어야 한다.
- 🏀 [ 답의 range를 정해서 답의 조건을 만족하는, 최대 or 최소값을 찾아나가는 것. ]🏀
- 첫 번째 집에 첫 번째 공유기를 설치한다고 했을 때, 그로부터 마지막 집까지의 거리를 max.
- min 과 max를 구해서 그 사이 range가 정답의 범위가 되도록 한다.
- min : 두 집 사이의 거리 중 최소값.
- 이 range에서 이분 탐색을 해 나간다. : 최대값을 찾아서.
- 조건 : 가장 인접한 거리가 해당 거리 + 공유기의 개수 C개를 설치 할 수 있어야 한다.
-
구현
- range에서 이분탐색을 이용한다. 현재 정한 거리 d 를 기준으로 한다.
- 첫 집부터 공유기를 설치하고 → 다음 집 : [ 공유기를 설치한 집과의 최소 거리(d)이상인 경우] 공유기를 설치한다. —> 이런식으로 공유기를 설치. —> C개의 공유기가 설치되는 경우와, 설치되지 않는 경우에 대해, d를 다르게 설정한다.
- C개의 공유기가 설치됨—> d를 늘린다 : 이분탐색의 우측으로 영역을 옮긴다.
- C개의 공유기 설치 실패 —> d를 줄인다 : 이분탐색의 좌측으로 영역을 옮긴다.
- When 탐색 종료?? —> Left > Right가 되었을 때.
- Left == Right 다음 경우가 Left > Right인 경우이다. 즉,
- Left == Right일 때, C개의 공유기 설치 fail할 수가 있다.
- 따라서 마지막으로 Success했을 때의 "거리"를 저장하고 있어야 한다 —> 이를 success라는 변수로 저장해 두는 것으로 구현.
- 🎈성능
- 이렇게 하면, 각각의 d에 대해 최대 n번의 비교 연산이 필요.
- 이분탐색이라면 각 d를 찾는데 O(logn)의 스텝이 필요.
- 즉, 총 O(nlogn) 의 성능을 가질 것.
- 집의 위치를 입력받는다.
- 10억1 크기의 배열을 생성한다.
- 집이 위치하는 곳을 1로 표시한다.
- 다음 집 사이거리를 계산하는 함수를 선언한다
- d보다 집사이 거리가 작아 다음 집으로 넘어가는 경우, 누적할 수 있어야 한다.
💥주의
- 가장 마지막으로 조건을 모두 만족했을 때의 "거리"를 저장해 둬야 한다.
--> Find할 때 마다 변수 "success"에 "해당 거리"를 저장.
#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> distance_v;
int dist_table[200001]; // store distance between houses .
int n, c;
int min_dist, max_dist; // min idx, max idx.
// target : Goal distance
/*
Return
-1 : d를 줄일 것
1 : d를 늘릴 것.
*/
int check(int target)
{
int cur = 0;
int temp_tot_distance = 0;
int cnt = 1; // the number of house installed. starting with first house.
while (cur < n-1 ) {
int distance = dist_table[cur]; // distance untill next home
temp_tot_distance += distance;
if (temp_tot_distance >= target) {
cnt++;
temp_tot_distance = 0;
}
cur++;
}
if (cnt >= c) return 1;
else return -1;
}
int my_bin_search()
{
int success=-1;
int left = min_dist, right = max_dist;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (check(mid)>0) {
left = mid + 1;
success = mid;
//cout << "Success : " << mid << endl;
}
else {
right = mid - 1;
}
}
return success; // left>right된 경우, success했던 case가 while문 안에 하나는 있을테니.
}
int main()
{
cin >> n >> c;
min_dist=1000000000, max_dist = 0;
// 각 집의 위치를 저장 벡터
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
distance_v.push_back(temp);
}
// 순서대로 정렬 --> 집의 거리 순 정렬
sort(distance_v.begin(), distance_v.end());
// 집 사이 거리 중 max값
max_dist = distance_v[n - 1] - distance_v[0];
// 모든 두 집 사이의 거리구하기.--> min찾아야.. -> min을 구하는데 O(n)
for (int i = 0; i < n - 1; i++) {
int dist = distance_v[i + 1] - distance_v[i];
dist_table[i] = dist;
if (min_dist > dist)min_dist = dist;
}
int result = my_bin_search();
cout << result;
}