문제 보기 · Level 4 · 이분탐색 · 정답률 32% · 푼 사람 9,745명 (2026-09-30 기준)1
문제
출발점(0)에서 distance만큼 떨어진 곳에 도착점이 있고, 그 사이에 바위들이 있다. 바위를 정확히 n개 없앤 뒤 출발점·바위·도착점 사이 거리들의 최솟값을 구한다. 없앨 바위를 잘 골라 이 최솟값을 가장 크게 하면 얼마인지 돌려준다.
- distance 1 ~ 1,000,000,000
- 바위 1 ~ 50,000개, 1 ≤ n ≤ 바위 수
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
매개변수 탐색: “최솟값의 최댓값”은 매개변수 탐색의 대표 신호다. “모든 간격을 d 이상으로 만들 수 있나?”로 바꾼다.
1단계 · 작은 예로 손으로 풀기
distance 25, 바위 [2, 14, 11, 21, 17], n = 2. 정렬하면 [2, 11, 14, 17, 21]이다.
“모든 간격을 4 이상으로” 만들어 본다. 앞에서부터 보며, 직전에 남긴 지점과의 거리가 4보다 작으면 그 바위를 없앤다.
- 2: 0과 2 차이 → 없앤다(1개).
- 11: 0과 11 차이 → 남긴다.
- 14: 11과 3 차이 → 없앤다(2개).
- 17: 11과 6 → 남긴다. 21: 17과 4 → 남긴다. 도착점 25: 21과 4 → 괜찮다.
2개만 없애면 된다. 5 이상으로는 3개를 없애야 해서 안 된다. 답은 4다.
2단계 · 가장 단순한 방법과 그 속도
없앨 바위 n개를 모두 고르면 조합 수가 C(50000, n)으로 폭발한다. 답 d를 1부터 하나씩 늘려 보는 것도 distance가 10억이라 안 된다.
3단계 · 핵심 아이디어
- 판정: “간격을 모두 d 이상으로 만들려면 바위를 몇 개 없애야 하나?”를 앞에서부터 욕심껏 센다. 직전에 남긴 지점과 d보다 가까우면 없애고, 아니면 남긴다. 필요한 수가 n 이하면 d는 된다(n보다 적게 없앴다면, 남은 바위를 더 없애도 간격은 줄지 않는다).
- 욕심이 맞는 까닭: 너무 가까운 바위를 남기면 그 간격이 이미 d보다 작다. 없애는 것 말고 방법이 없다. 멀리 있는 바위는 남겨야 다음 바위와의 간격을 넓게 쓸 수 있다.
- 도착점은 없앨 수 없다: 도착점이 직전 바위와 d보다 가까우면 그 직전 바위를 없앤 것으로 하나 더 센다. 그 바위를 없애면 도착점과 그 전 지점 사이는 d보다 넓어진다.
- 방향: d가 크면 더 많이 없애야 한다. 된다…된다 안 된다…안 된다의 최대형이다. 범위는 0 ~ distance다. lo는 늘 “된다”, hi보다 큰 값은 늘 “안 된다”인 채로 구간을 반씩 줄인다. 양 끝의 부호가 다른 구간을 반씩 줄여 근을 찾는 이분법과 같은 틀이다. 다만 이분법은 근이 여럿이면 그중 하나를 찾지만, 여기서는 대답이 한 번만 바뀌어서 찾은 경계가 곧 하나뿐인 답이다.
4단계 · 코드 흐름
- 바위를 정렬한다.
- removed_needed(d): prev = 0에서 시작해 바위들과 도착점을 차례로 보며, x − prev < d면 개수를 1 늘리고, 아니면 prev = x.
- lo = 0, hi = distance로 최대형 틀을 돌린다. removed_needed(mid) ≤ n이면 lo = mid.
5단계 · 파이썬 코드
def solution(distance, rocks, n):
rocks = sorted(rocks)
def removed_needed(d):
cnt, prev = 0, 0
for x in rocks + [distance]:
if x - prev < d:
cnt += 1 # x를 없앤다(도착점이면 직전 바위를 대신 센다)
else:
prev = x
return cnt
lo, hi = 0, distance
while lo < hi: # 최대형 틀
mid = (lo + hi + 1) // 2
if removed_needed(mid) <= n:
lo = mid
else:
hi = mid - 1
return lo
rocks + [distance]: 도착점을 마지막 지점으로 붙여 같은 규칙으로 본다.- 도착점이 너무 가까울 때 cnt만 늘리고 prev는 그대로 둔다. 그 뒤에 볼 지점이 없어 prev는 더 쓰이지 않는다.
6단계 · 실행 추적
distance 25, 바위 [2, 11, 14, 17, 21], n = 2
| lo | hi | 물어본 d | 없애야 할 수 | 판정 |
|---|---|---|---|---|
| 0 | 25 | 13 | 5 | 안 된다 → hi = 12 |
| 0 | 12 | 6 | 3 | 안 된다 → hi = 5 |
| 0 | 5 | 3 | 1 | 된다 → lo = 3 |
| 3 | 5 | 4 | 2 | 된다 → lo = 4 |
| 4 | 5 | 5 | 3 | 안 된다 → hi = 4 |
답은 4다.
7단계 · 복잡도와 흔한 실수
판정 \(O(N)\) × 약 log₂(10억) ≈ 30번, 정렬 \(O(N \log N)\)이다. 바위 5만 개로 재 보니 0.1초가 안 걸렸다.
- 바위를 정렬하지 않는다.
- 도착점까지의 마지막 간격을 판정에서 빼먹는다.
- “정확히 n개”에 매달려 판정을
== n으로 한다. n개보다 적게 없애도 되면 남은 바위를 더 없애 정확히 n개로 맞출 수 있다.
검증: 문제의 예시를 통과했고, 6단계의 물어본 d와 판정 값을 코드로 확인했다. 무작위 입력 3,000개(서로 다른 바위 위치)에서 “없앨 바위 n개를 모두 골라 보는” 풀이와 결과가 같았다. 바위를 모두 없애는 경우와 5만 개의 시간도 확인했다 — 21_pg43236_p1.py