[코딩테스트 연습] 징검다리

 

문제: https://programmers.co.kr/learn/courses/30/lessons/43236

---

이분 탐색 문제입니다.

 

10억에 해당하는 distance를 선형 탐색하면 O(10억)으로 시간초과가 납니다.

 

그러므로 5만에 해당하는 바위 갯수를 이용해서 문제를 해결해야 합니다.

 

아이디어는 다음과 같습니다.

 

1. 임의의 바위 간의 거리를 정합니다. (mid)

2. 이 바위 거리를 정답으로 할 때 n개 이하의 돌을 제거할 수 있는 지 세봅니다.

3-1. 2번이 가능하다면 바위 거리를 정답후보로 저장하고, 바위 간의 거리를 증가 시켜봅니다.

3-2. 2번이 불가능하다면 바위 간의 거리를 줄여봅니다.

 

이런 식으로 이분 탐색을 하면 됩니다.

단, 2번에서 n개 '이하'의 돌에 적용할 수 있는 것은 예를 들어, 정답이 n- 2개 돌만 치워도 가능하다면,

2개의 돌을 추가로 없애도 정답인 최소 거리는 줄어들지 않습니다.

왜냐면 돌을 치울수록 돌 간의 거리는 늘어날 뿐 절대 줄어들지 않기 때문입니다.

위 성질이 있기 때문에 n개 이하의 돌을 제거할 수 있다면 n개의 돌을 제거하는 것으로 놓아도 무방합니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43236.cc