문제 출처 : https://www.acmicpc.net/problem/2110
문제 파악
집의 개수 N (2 ≤ N ≤ 200,000), 각 집의 좌표 xi (0 ≤ xi ≤ 1,000,000,000) 를 입력받고,
설치할 공유기의 개수 C (2 ≤ C ≤ N) 를 입력받는다.
우리가 구해야 할 것:
“가장 인접한 두 공유기 사이의 거리를 가능한 크게 했을 때, 그 최대 거리”
예제를 보자.
- 집의 개수
5 - 집의 좌표:
[1, 2, 8, 4, 9] - 설치할 공유기 개수:
3
집을 정렬하면: [1, 2, 4, 8, 9]
이때 예를 들어,
1, 4, 8에 설치하거나1, 4, 9에 설치하면
서로 인접한 두 공유기 사이의 거리들 중 최소값은 3이 된다.
그리고 이 3보다 더 크게 만들면서 3개를 설치하는 건 불가능하다고 한다.
즉, 집들 중에서 C개를 골라 공유기를 설치할 건데,
“공유기들 사이의 최소 거리를 최대화해야 하는 문제”
라고 정리할 수 있다.
집 좌표 범위가 1,000,000,000 으로 매우 크기 때문에
공유기 위치를 전부 완전탐색하는 건 불가능해 보인다.
공유기의 위치에 따라 두 집 사이의 거리가 단조적으로 증감하기에 이 문제는 이분탐색 으로 풀 수 있다.
최소 거리를 mid (answer) 로 잡고 적당히 이분탐색해야 하는 것 까진 떠올렸지만 그 공유기를 설치 가능한 지 아닌 지에 대한 로직을 떠올리지 못해 내 손으로 풀진 못했다.
GPT의 풀이는 can_install 이라는 함수를 만들어서 깔끔하게 이분탐색 로직에 함수를 넣어서 풀었다.
GPT 풀이에서는 can_install(dist)라는 함수를 만들어서
이분 탐색 로직 안에서 사용했다.
“공유기 사이 최소 간격을 dist 이상으로 유지하면서,
C개 이상 설치할 수 있는지”
- 가능하면 →
True - 불가능하면 →
False
라는 bool 값을 반환한다.
can_install(dist) 함수
def can_install(dist):
count = 1 # 맨 첫 번째 집에는 무조건 설치한다고 가정하고 시작
last = houses[0] # 마지막으로 공유기를 설치한 집의 좌표
for i in range(1, N):
# 현재 집과 마지막 설치 위치 사이의 거리가 dist 이상이면 설치 가능
if houses[i] - last >= dist:
count += 1
last = houses[i] # 마지막 설치 위치 갱신
# return 값으로 True or False 반환
return count >= C해답 및 풀이
import sys
input = sys.stdin.readline
N, C = map(int,input().split())
houses = [] # 좌표 담을 배열
for _ in range(N):
houses.append(int(input()))
# 집 좌표 정렬: 왼쪽에서 오른쪽 순으로 탐색하기 위해 필수
houses.sort()
answer = 0
# "공유기 사이 최소 간격을 dist 이상으로 유지하면서, C개 이상 설치할 수 있는지"
# → 가능하면 True, 안 되면 False를 반환.
def can_install(dist):
count = 1 # 맨 첫번째 집에는 무조건 공유기 하나 박고 시작
last = houses[0] # 마지막으로 설치한 집의 좌표,
for i in range(1,N):
if houses[i] - last >= dist:
count += 1
last = houses[i]
# count >= C → 설치 가능 → True
# count < C → 설치 불가 → False
return count >= C
left = 1
right = houses[-1] - houses[0]
while left <= right:
mid = (left + right) // 2
if can_install(mid):
answer = mid
left = mid + 1
else:
right = mid - 1
print(answer)can_install 함수를 따로 만드는 것과
return 값에 count >= C 이런식으로 부등호를 넣어 bool 값으로 반환하는 스킬을 볼 수 있었다.
다시 푼 코드
import sys
input = sys.stdin.readline
N, C = map(int,input().split())
houses = []
for _ in range(N):
houses.append(int(input()))
houses.sort()
answer = 0
def can_install(dinstance):
install = 1
first = houses[0]
for i in range(1,N):
if houses[i] - first >= dinstance:
install += 1
first = houses[i]
return install >= C
left = 1
right = houses[-1] - houses[0]
while left <= right:
mid = (left + right) // 2
if can_install(mid):
answer = mid
left = mid + 1
else:
right = mid - 1
print(answer)