문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
2110번: 공유기 설치 문제 보러 가기
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 입력 1
5 3
1
2
8
4
9
예제 출력 1
3
힌트
공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.
1,2,4,8,9 에 3개의 공유기를 위치시키는데
가장 인접한 두 공유기 사이의 거리가 최대로 해서 그 최대 거리 출력
가장 왼쪽과 가장 오른쪽 위치의 중간값인 5를 두 공유기 사이의 거리라고 했을때,
3개를 둬야하는데 1에 두고 8에 두면 9에는 둘수가 없음
이런식으로 반복하며 확인
정답
import sys
sys.stdin=open('input.txt','r')
def Count(mid): # 서로 적어도 mid 만큼 떨어져있다고 할때 C이상 공유기를 놓을 수 있을까?
cnt=1 # 공유기 하나를 배치한다
sp=loc[0] # start point 첫번째 공유기부터 살펴보자
for i in range(1,N):
if loc[i]-sp>=mid: # 현재위치와 첫번째 공유기 위치간의 거리가 가정한 mid값보다 크면
cnt+=1 # cnt 증가 -> 공유기를 놓음
sp=loc[i] # 공유기를 놓았으니 새로운 위치로 업데이트됨
# 그리고 계속 다음 공유기 살펴봄
return cnt
if __name__=="__main__":
N,C=map(int, input().split()) # 집의 개수:N, 공유기 개수:C
loc=[] # 집 좌표
loc=[int(input()) for _ in range(N)]
loc.sort()
res=0
start=1
end=loc[-1]
while start<=end: # start가 end보다 커지면 그만
mid=(start+end)//2 # 가장 가까운 거리가 가운데 값이라고 가정해봄, 즉 적어도 mid만큼은 서로 떨어져 있어야함
if Count(mid)>=C: # 조건을 만족하며 Count(mid)가 원하는 공유기 개수만큼 또는 더 많이 놓을수 있을때
res=mid
start=mid+1 # 조건을 만족하는 거리보다 작은 값은 볼필요없음->start 업데이트->더큰 mid값을 살펴봄으로써 더 큰 거리를 살펴봄
else: # 인접한 두 공유기간의 거리가 너무 길어서 C개를 다 못 놓음 -> mid 이것보다 더 긴 거리는 볼 필요 없음
end=mid-1
print(res)
