1, 2와 1, 4의 거리는 갭에 4이하이므로 1,8밖에 설치가 안되며, 8,9 또한 갭이 1이 안되므로 전체 공유기 개수는 2개 되어 다시 Gap를 감소시킨다.이 때 최대 gap은 이전 mid Gap 보다 1을 줄여서 최대 gap으로 설정한다.
현재 미드 gap 값은 다시 계산(min+max //2) 2가 된다.
2를 기준으로 아까처럼 1,2는 x 1,4는 o 4,8은 o 8,9는x로 공유기를 3개까지 설치가 가능하다.
현재 미드 gap 값을 결과 값에 저장하고 가장 큰 경합값을 찾기 위해 최소 gap 값을 증가 시킨다.
서로 만나는 지점의 gap이 되었으므로 미드 gap 또한 3이된다.
1,2x 1,4o 4,8 o, 8,9x로 공유기 3개 조건을 만족하므로 결과값에 현재 gap으로 다시 대입한다.
n, c = map(int, input().split())
array = []
for _ in range(n):
array.append(int(input()))
# n,c = 5, 3
# array = [1, 2, 8, 4, 9] #
array = sorted(array)
min, max = 1, array[-1] - array[0]
result = 0
while (min <= max): # 이진 탐색
mid = (min+max) // 2 # 4, 3.....
value = array[0]
count = 1
for i in range(1, len(array)): # 각 데이터를 돌면서 mid 간격 비교
if array[i] >= mid+value: # 만약 현재 값이 설정한 mid 값 이상이면
count +=1 # 공유기 추가
value = array[i] # 다음 데이터 비교를 위한 value 값 대입
if count >= c: # 공유기 개수가 맞으면
result = mid # 공유기 결과 저장
min = mid + 1 # 더 넓은 폭을 찾기 위해 처음 값 mid +1 로 대입
else:
max = mid - 1 # 더 좁은 폭을 찾기 위해 end 값 mid-1로 대입
print(result)
min, max 값 "min, max = array[1] - array[0], array[-1] - array[0]" 영번 째 인덱스 기준으로 거리를 최대 최소로 구함.
min 값을 array[1] - array[0]으로 하니 정답이 계속 틀리다고 나옴. min 값을 1로 고정해주니 정답 처리됨.
"while"문은 이진탐색 시 "min", "max" 증 가감하면서 만나기 때문에 그 때까지 반복을 함
"mid" 중간 값 설정하고 여기서 중요한건 "value" 값
value값이 간격을 계속 체크하기위한 값이 됨
"for i in range(1, len(array)): # 각 데이터를 돌면서 mid 간격 비교 "을 통해 각각의 데이터 비교 시작
"if array[i] >= mid+value" # 만약 현재 값이 설정한 mid 값 이상이면 count +=1 # 공유기 추가 value = array[i] # 다음 데이터 비교를 위한 value 값 대입
헷갈린 이유가 계속 "value" 누적이유
1,4,7,10 배열로 계속 들어오는 상황에서 인덱스 비교를 배열[1]부터 시작하며 mid가 3으로 가정을 하면
1,4 비교시 4와 1의 간격이 3이 되었을 때 value 값을 다시 array[i] 로 해줘야 다음 값 4, 7을 현재 간격으로 해서 계속 비교할 수 있음
비교가 끝난 뒤 만약 공유기 개수가 입력 m 값이면 -> 즉 start 값을 mid+1로 증가 해서 간격을 늘리는게 목적
