백준2110(파이썬) - 공유기 설치

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

• 이 문제를 읽고 이분탐색을 써야할 꺼같긴한데... 였다.
• 이분탐색으로 찾아야 할 것, 즉 여기서는 뭐를 변수로 두냐인데 문제에서 구하라는게 간격이므로 간격을 변수로 두고 이분탐색을 돌렸다.
• 집의 좌표를 담은 리스트를 오름차순 정렬시켜서 나타내주고, 한 좌표에 이분탐색으로 구한 간격을 더하면 다음 좌표가 가능한지를 찾으면서 알고리즘을 짰다.
• 여기서 내가 했던 실수는 이분탐색을 돌릴 때, start 값과 end 값을 설정하는 과정에서 end값은 맞게 설정했지만, start값은 list[1] - list[0] 로 설정했는데, 이 경우에는 1,7,8,9,10 이라는 데이터가 주어지면, 올바르게 실행되지 않는다. 그래서 start는 모든 좌표사이의 최솟값인 1로 설정했더니 맞았다.

import sys
input = sys.stdin.readline

n,c = map(int,input().split())
data = []
for _ in range(n):
    data.append(int(input()))
data.sort()

start = 1
# start = data[1]- data[0] 이경우에 5,3, 1,7,8,910 이렇게 넣으면 반례가생긴다.
end = data[-1] - data[0]
ans = 0
while start<=end:
    #while문 한바퀴돌때마다 data[0]값으로 시작하고
    flag = data[0]
    cnt = 1
    # mid는 간격이다.
    mid = (start+end)//2
    for i in range(1,len(data)):
        # while문을 통해 정해진 mid값을 각각 집 좌표마다 for문으로 돌려서 가능한지 가능하지 않은지 확인한다.
        if data[i]>=flag+mid:
            # 다음집을 검색한다.
            flag = data[i]
            # 집 카운트해준다 (카운트가 주어진다.)
            cnt+=1
    if cnt<c:
        end = mid-1
    else:
        start = mid+1
        ans = mid
print(ans)