[백준] 2110 공유기 설치

백준 2110번 공유기 설치

이분 탐색 / 매개 변수 탐색

 

 

 

[문제]

 

좀 어려웠던 문제

해당 알고리즘을 떠올리는 방법이 어려웠다.

풀이시간도 50분으로 길던것이 이해가 갔다. 시간 더 필요할듯..ㅋㅋ

 

'해당 풀이는 답지를 참고하였음'

 

'가장 인접한 두 공유기 사이의 거리를 최대로 하는 값'을 구하기

 

 

 

 

[과정]

• 데이터 정렬(오름차순) 수행
• 이진탐색 수행
  • 임의로 mid값((start + end) // 2)을 가장 인접한 두 공유기 사이로 설정
  • 해당 mid값만큼 이동하며 공유기 설치
  • 만약 공유기 설치 개수가 c개 이상이 되면
    • 현재 공유기 설치 개수 저장 후 '가능한 최소 거리'를 1 증가
  • 만약 c개의 공유기를 설치 할 수 없다면
    • '가능한 최대 거리'를 1 감소
• 결과(result) 출력

 

 

한줄 정리 - gap(mid)값을 임의로 설정 후 해당 값만큼 공유기를 설치하면서 이동하다가 'mid값을 조정'하는 방식

 

 

 

 

[소스코드]

 

import sys
input = sys.stdin.readline

# 집의 개수(N)와 공유기의 개수(C)를 입력 받기
n, c = list(map(int, input().split(' ')))

# 전체 집의 좌표 정보를 입력 받기
array = []
for _ in range(n):
     array.append(int(input()))
array.sort() # 이진 탐색 수행을 위해 정렬 수행

start = 1 # 가능한 최소 거리(min gap)
end = array[-1] - array[0] # 가능한 최대 거리(max gap)
result = 0

while(start <= end):
    mid = (start + end) // 2 # mid는 가장 인접한 두 공유기 사이의 거리(gap)을 의미
    # 첫째 집에는 무조건 공유기를 설치한다고 가정
    value = array[0]
    count = 1
    # 현재의 mid 값을 이용해 공유기를 설치하기
    for i in range(1, n): # 앞에서부터 차근차근 설치 
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c: # C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가시키기
        start = mid + 1
        result = mid # 최적의 결과를 저장
    else: # C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소시키기
        end = mid - 1

print(result)

 

 

---

 

 

[통과]

 

파이썬 시간 초과 날 때 꼭 쓰기..

 

import sys
input = sys.stdin.readline

 

// 백준을 풀었는데 포스팅이 살짝 밀려서 3일치 한번에 올린당~