문제 링크
https://www.acmicpc.net/problem/2110
문제 유형
이분탐색
🌈 문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
5 3
1
2
8
4
9출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
3💡 아이디어
아직은 복잡한 문제에 이분 탐색을 어떻게 적용해서 풀어야 하는지 감이 덜 잡힌 것 같다. 이 문제도 이분 탐색으로 간단하게 풀이할 수 있었는데 괜히 좌표 간 사이 거리에 대한 이차원 배열까지 상상하면서 풀이할 수 없는(?!) 복잡한 영역까지 가버린 것 같아서 다른 분들의 풀이를 참고해서 감을 잡아보려고 한다.
이분탐색의 아이디어와 알고리즘 코드 자체는 크게 어렵지 않은데 막상 문제에 적용하려고 하면 턱 막히는 기분이 든다. 유형에 단단해지도록 하자.
이 문제는 가장 인접한 두 공유기 사이의 거리가 최대가 되도록 해야 한다. 특이하다.
공유기를 설치해야 될 장소를 먼저 찾아서 그 둘 사이의 거리를 구하는 것이 이 문제의 관건이라고 할 수 있는데
모든 집과 그에 대한 거리를 구하고자 하면 집의 최대 개수는 200,000개이기 때문에 당연히 시간 초과 오류가 발생하게 된다. 그래서 이분 탐색을 이용하여 공유기를 설치하게 될 집들을 조사하는 것이다.
아래와 같은 순서대로 코드의 흐름을 작성하면 된다.
- 집들의 좌표를 입력받는다.
- 최소 거리와 최대 거리를 설정해둔다.
- 앞 집부터 공유기를 설치하면서, 설치할 수 있는 공유기 개수가 C개를 넘어가게 되면 더 넓은 범위로 설치할 수 있으므로, 설치 거리를
mid + 1로 설정하여 다시 앞의 집부터 공유기를 재설치한다. - 만약 공유기 개수가 C개를 넘어가지 않게 설치된다면 더 좁은 범위에서 설치를 진행해야 하므로
mid-1로 설정하고 공유기를 재설치한다.
👨💻 코드 작성
N, C = list(map(int, input().split()))
arr = []
answer = 0
for _ in range(N):
arr.append(int(input()))
arr.sort() #정렬
start = 1 #최소 거리 설정
end = arr[-1] - arr[0] #가장 큰 값 - 가장 작은 값 (최대 거리)
while start <= end:
mid = (start + end) // 2 #중간값
cur = arr[0] #첫번째 좌표
cnt = 1
for i in range(1, len(arr)):
if arr[i] >= cur + mid:
cur = arr[i]
cnt += 1
if cnt >= C:
start = mid + 1
answer = mid
else:
end = mid - 1
print(answer)이 문제는 코드로는 이해될 수 있는데 머리로 끝까지 이해한다는 것은 여간 쉬운 일은 아닌 것 같다.
정답으로 삼을 수 있는 최소 간격의 최대 거리를 1부터 max 거리까지 모두 살펴보기가 어려우니, 그의 중간값인 mid로 먼저 거리를 하나하나 탐색해본다는 점에서 이분탐색을 최대한으로 활용할 수 있었다는 점을 기억해 두면 될 것 같다 :)
