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

 

2110번: 공유기 설치

이 문제는 이코테 떡볶이 만들기 문제와 아주 유사하다.

이진탐색 유형 문제로, 탐색을 시간적인 면에서 효율적으로! 찾을 수 있는 알고리즘: 이진탐색을 이용하는 문제다.

1.  문제를 풀기 위한 아이디어 : 핵심

- 가장 인접한 공유기 사이의 거리가 될 수 있는 범위: 1 ~ (제일 큰 좌표 - 제일 작은 좌표)
- 이진 탐색으로 구한 해당 거리가(mid) 가장 인접한 공유의 사이의 거리로 두고 설치가 가능한가 확인 => 주어진 좌표들 모두 target거리 이상으로 떨어지게 설치가 가능한지 확인.

2. 코드

import sys
input = sys.stdin.readline
n, c = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))

result = 0
arr.sort() # 이진탐색은 정렬되어 있음을 가정한 탐색이다.
def sol(s, e):
    global result
    while s <= e:
        cnt = 1 # 일단 맨 앞 좌표는 바로 설치함. 설치는 그 이후부터 확인.
        current = arr[0]
        mid = (s+e)//2 # 구한 거리.
        for i in range(1, n): # 모든 좌표위치에서 가장 인접한 거리가 될 수 있는지 확인.
            if arr[i] >= current + mid:
                current = arr[i]
                cnt += 1
        if cnt >= c: # 만약 주어진 좌표 모두 mid 거리로 설치 가능 하다면, 값을 저장하고, s = mid + 1써서 결과값의 범위를 높인다.
            result = mid
            s = mid + 1
        else:
            e = mid - 1

    return result

    
print(sol(1,arr[-1] - arr[0]))

 

 

참고

[백준] 2110번 공유기 설치 (Python 파이썬)