[알고리즘] 백준2110 공유기 설치 - 파이썬

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

2110번: 공유기 설치

 

 

[풀이 코드]

from sys import stdin

n, c = map(int, stdin.readline().split())
a_list = [int(stdin.readline()) for _ in range(n)]
a_list.sort()

start = 1
end = a_list[-1] - a_list[0] # 끝집과 처음집을 뺴준 총 거리

result = 0 # 결과값 저장
while start <= end:
    mid = (start + end) // 2

    selected = a_list[0]
    cnt = 1 # selected 로 첫집을 선택했으니 카운트를 하나 올려준 상태로 저장
    for i in range(1, len(a_list)):
        if a_list[i] >= selected + mid: # 선택된 집좌표 + 탐색거리(mid)가 이동할 집좌표보다 작거나 같다면
            cnt += 1
            selected = a_list[i] # 이동할 좌표

    if cnt >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

- 이분 탐색으로 풀어야 된다는 걸 알았지만 제멋대로 풀다가 시간을 많이 버린 문제.. 결국 다른 분의 풀이를 보면서 이해했습니다.

 

- end는 끝 좌표와 첫 좌표를 빼주어 가능한 총거리를 저장합니다.

 

- selected에는 선택된 맨 첫 좌표부터 mid(거리) 값을 더해주며 반복문(for문) 안에서 이동 가능한 집을 탐색합니다. 또 이동 가능할 때마다 cnt를 올려줍니다.

 

- 나머지 부분은 일반적인 이분 탐색을 위한 코드라 설명하지 않겠습니다. 중요한 로직은 주석을 자세히 달아놨습니다.

 

 

 

[참고 블로그]

---

https://assaeunji.github.io/python/2020-05-07-bj2110/

[백준] 2110 공유기 설치 파이썬 풀이