출처: https://www.acmicpc.net/problem/2110
문제 분석
우선 시간제한은 2초이다. 그런데 N이 200000까지 주어져있다. 따라서 NlogN의 복잡도로 구현을 해야함을 눈치챌 수 있다. 물론 이런 유형은 이분탐색으로 하는게 국롤이다
그런데, 일단 문제를 해석하는 것 부터가 쉽지않다. 가장 인접한 두 공유기 사이의 거리를 최대로 해라..? 이 문제를 읽고 내 심정은 정말 아래의 그림과 같았다...
정말 이 그림만큼 내 심정을 대변하는건 없을거다...
그래도 문제를 분석하다보면, 정말 의구심이 많이 든다. 내가 들었던 의구심은 이러했다.
- 이분탐색을 해야하는건 알겠는데, mid를 설정해도 mid만큼의 간격이 딱 떨어지는 경우가 없을 수도 있잖아..? 이건 어떻게 해야함?
- start, end를 조절하는 조건은 어떻게 해야함..? 막막하다.
사실 위에 적은 것보다 몇 배로 고민은 한 것 같다. 결과적으로 나는 이러한 결론에 도달했다.
일단 앞집부터 공유기를 계속 깔아보자. mid로 딱 떨어지지 않는 경우도 있겠지만, 딱 떨어지면 좋고, 아니여도 그냥 go하자.
그런데 이런 의문도 들 수 있다.
만약에 mid로 딱 떨어지는게 중간부터 등장하면 어떡할래?
그런데 첫 집부터 mid로 딱 떨어지지 않는 경우는, mid보다 큰 간격으로 두번째 집이 등장할 경우이므로, 위에서 생각한대로 진행해도 문제는 없을것이다!
이러한 생각으로 코드를 구성해보았다. 코드를 확인해보자!
코드를 확인해봅시다
import sys
# 2110번 문제
input = sys.stdin.readline
N, C = map(int, input().split())
coordinate_list = []
for _ in range(N):
coordinate_list.append(int(input()))
coordinate_list = sorted(coordinate_list) # 정렬
start, end = 1, coordinate_list[N - 1] - coordinate_list[0]
# 탐색 시작
while start <= end:
mid = (start + end) // 2
count = 1
current_house = coordinate_list[0]
# 앞집에서 부터 공유기 심기
for i in range(1, N):
if coordinate_list[i] - current_house >= mid:
count += 1
current_house = coordinate_list[i]
if count >= C:
start = mid + 1
else:
end = mid - 1
print(end)일단 입력받은 리스트를 정렬해줬다. 앞집부터 공유기를 깔아보기로 했기 때문이다.
그리고 start는 1, end는 첫 집과 끝 집의 거리 차로 정했다. 그리고 이분탐색을 돌면서 공유기를 첫 집부터 쫙 깔기 시작한다.
mid = (start + end) // 2
count = 1
current_house = coordinate_list[0]일단, 기본적인 아이디어는 과연 앞 집부터 공유기를 깔아서, C만큼의 집에 공유기를 깔 수 있을까? 를 체크해보자는 것이다. 만약에 깔지 못하면, 그거는 범위를 너무 넓게 잡았기 때문이고, 깔 수 있다면 범위를 조금 넓게 잡아도 괜찮다는 뜻일것이다!
# 앞집에서 부터 공유기 심기
for i in range(1, N):
if coordinate_list[i] - current_house >= mid:
count += 1
current_house = coordinate_list[i]current_house에는, 이전에 공유기를 심었던 집의 좌표가 저장되어있다. coordinate_list를 탐색하면서 mid보다 큰 간격을 가졌는지 검사를 하고, 조건을 만족하면 공유기를 심어주자는 것이다.
공유기를 다 심게되면, C의 조건에 따라서 start, end를 조절하면된다.
마지막으로, end를 출력하면 문제는 모두 해결된다!
