문제
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있음
rocks배열 중 n개를 제거했을 때 각 지점 사이 거리의 최솟값 중 가장 큰 값은?
생각할 것
- mid : 각 지점 사이의 최대 거리를 의미
- 가장 가까운 돌과의 거리를 mid와 비교하고 더 작으면 돌을 빼준다.
- 돌을 뺀 갯수가 빼야하는 개수보다 크면 목표 거리를 줄임
- 돌을 뺀 갯수가 뺴야하는 개수보다 작으면 돌을 더 놓을 수 있으므로 목표 거리를 늘림
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
vector<bool> r(rocks.size(), true);
int answer = 0;
int left = 0;
int right = distance;
sort(rocks.begin(), rocks.end());
while(left <= right) {
int mid = (left + right) / 2;
int prev = 0;
int rock_cnt = 0; // 뺀 돌의 개수
for(int i = 0; i < rocks.size(); i++) {
if(rocks[i] - prev < mid) rock_cnt++; // 최대 거리보다 작으니 돌을 빼서 거리를 늘려줘야함
else prev = rocks[i]; // 최대 거리보다 같거나 크므로 돌을 그대로 둠
}
if(distance - prev < mid) rock_cnt++; // distance와의 거리 비교
if(rock_cnt > n) { // 돌을 너무 많이 뺐으므로 목표거리를 줄여야 함
right = mid - 1;
}
else { // 돌을 너무 적게 뺐음 목표거리를 늘려서 더 많은 거리 두게 해야함
answer = max(answer, mid);
left = mid + 1;
}
}
return answer;
}
주의할 것
처음부터 돌 사이의 거리 말고도 끝 distance거리도 생각해야한다!
반응형
'Problem solving > Programmers' 카테고리의 다른 글
[Programmers] 여행경로 (C++) (0) | 2023.07.05 |
---|---|
[Programmers] 단어 변환 (C++) (0) | 2023.07.05 |
[Programmers] 게임 맵 최단거리 (C++) (0) | 2023.07.05 |
[Programmers] 입국심사 (C++) (0) | 2023.07.04 |