https://www.acmicpc.net/problem/6209
문제
> GSHS에서는 체력측정에서 제자리 멀리뛰기가 가장 중요하다.
> GSHS의 체육선생님께서는 학생들의 제자리 멀리뛰기 실력을 키워주게 하기 위해서 특수 훈련을 준비중이다.
> 특수 훈련장소는 GSHS특수 트레이닝 센터로 이 곳은 끓는 용암으로 가득 차 있다.
> 체육선생님께서는 이 용암으로 가득찬 방의 가운데 있는 돌섬에 학생들을 가두고 학생들이 탈출해 나오기를 기대하고 있다.
> 탈출할 수 있는 방법은 단 한가지 이다.
> 돌섬에서 탈출구까지 띄엄 띄엄 존재하는 작은 돌섬들로 점프하여 탈출구까지 가는 것이다.
> 돌섬에서 탈출구 사이에는 총 n개의 작은 돌섬이 있다.
> 선생님은 이 n개의 작은 돌섬들 중 m개를 제거하여 학생들이 최대한 멀리뛰기 연습의 효율을 높이기 위해서 학생들이 각 돌섬을 점프한 거리의 최솟값을 최대한 크게 하려고 한다.
> 물론 학생들은 체력이 좋기 때문에 두 돌섬이 아무리 멀더라도 점프할 수 있다.
> 즉, 빠지는 일은 없다.
> 그리고 학생들은 탈출 시 n-m개의 모든 돌섬을 밟으면서 탈출해야 한다.
> 학 생들이 갇힌 돌섬으로부터 탈출구까지의 거리 d가 주어지고,
각 n개의 작은 돌섬의 위치(갇힌 돌섬으로 부터의 거리)가 주어지며,
제거할 수 있는 작은 돌섬의 수 m이 주어질 때,
> m개를 제거한 후 학생들이 점프하는 최소거리의 최댓값을 구하는 프로그램을 작성하시오.접근
학생이 뛸 수 있는 점프거리의 최소값을 이분탐색의 mid값으로 잡아준다. 처음엔 시작점,끝점을 기준으로 잡고 시작 점부터 다음 돌 까지의 거리를 본다. 이 mid보다 작으면 더 뛸 수 있는데 낭비하는 것이므로 제거한다.
제거하고 난뒤 다시 처음부터 다음 돌 까지 뛴다. mid보다 크면 해당 돌을 시작점으로 잡고 다음돌까지 뛴다. 이 과정을 반복하는데 제거된 돌의 개수가 M보다 크면 점프의 최소거리를 좀 줄여야한다. 시작점, 중앙값-1로 다시 중앙값을 세팅하고 M보다 작으면 충분하긴 한데 최적을 구하기 위해 중앙값+1, 끝점을 기준으로 중앙값을 구하며 최적을 찾는다.
문제해결
> 주어진 끝점, 돌 개수, 제거가능한 돌 개수를 입력받고 돌 개수+1개 크기의 돌 위치 벡터를 선언한다.
> +1개인 이유는 끝점인 도착지점도 따져주기 위해서이다.
> 돌 위치를 모두 입력받고 추가로 끝점도 입력해준뒤 위치 기준 오름차순 정렬해준다.
> 점프거리를 구하는 Find메소드에선 시작점, 끝점을 인자로 가지며 이분탐색을 한다.
> left,right값으로 mid값을 구하고, 시작점을 prev로 가지며 돌을 순회하며 비교한다.
> prev부터 돌 위치까지의 거리가 mid보다 작으면 더 뛸 수있기 때문에 돌을 제거하고 삭제한 돌 수를 누적한다.(cnt)
> mid보다 크면 충분하므로 해당 돌을 prev로 주고 해당 위치부터 뛴다.
> 모든 돌에 대해 위 과정이 끝난 후 cnt가 m보다 크면 제거가능한 돌의 수를 넘어갔으므로 점프 거리를 줄여야한다.
> 따라서 right값을 mid-1로 갱신하고 다시 위 과정을 반복한다.
> m보다 작다면 충분하지만 더 최적의 답을 구하기 위해 점프 거리를 좀더 늘려 본다. left = mid+1
> 최적의 거리가 구해지면 right가 최적의 점프 거리의 최소값중 최대값이므로 right를 반환해 출력한다.코드
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int d, n, m;
vector<int> stone;
int Find(int start, int end)
{
int left = start;
int right = end;
int mid = (left + right) / 2;
while (left <= right)
{
int cnt = 0;
mid = (left + right) / 2;
int prev = 0;
for (int i = 0; i <= n; i++)
{
if (stone[i] - prev < mid)
{
cnt++;
continue;
}
prev = stone[i];
}
if (cnt > m)
{
right = mid - 1;
continue;
}
left = mid + 1;
}
return right;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> d >> n >> m;
stone.resize(n+1);
for (int i = 0; i < n; i++) cin >> stone[i];
stone[n] = d;
sort(stone.begin(), stone.end());
cout << Find(0, d) << '\n';
}
후기
이분탐색의 mid를 뭘로 정할지가 젤 고민이었다. 머릿속으론 모든 돌의 탐색을 한다고 했지만 도착지점을 빼먹고 있었다. 이를 수정해주니 맞았다.
