문제
Albert는 L대학에서 주최하는 Hackathon 행사 진행을 도와주기로 했는데, 사회적 거리 두기 방침에 따라 모든 참가자들을 최대한 멀리 떨어트려 좌석 배정을 해주려 한다. 이를 위해 아주 길다란 복도를 따라 특정 위치에 모니터, 책상, 의자를 두는 식으로 좌석을 배정하고, 각 좌석에는 최대 한 팀만 착석할 수 있다. 총 s개의 팀이 행사에 참가하고, 복도를 따라 총 n곳에 전원 공급이 가능한 콘센트가 설치되어 있다 -- 좌석은 반드시 콘센트가 설치된 곳에만 할 수 있다. 편의상 콘센트가 설치된 지점들의 위치를 x[1], x[2], ..., x[n] 이라 하자 (각 x[i]는 복도 입구로 부터의 거리를 나타낸다). 즉, i번째 콘센트는 복도의 입구로부터 x[i] 만큼 떨어진 곳에 있다.
Albert는 n개의 콘센트 위치 중 s개를 선택하여 좌석을 선택하되, 가장 가까운 두 좌석의 거리 (D라 하자)가 최대가 되도록 하고 싶다.
예를 들어, n = 3, s = 3 이고 x = [10, 100, 200]이라 하자. 이 경우 n = s 이므로 각 콘센트 위치에 좌석을 설치해야 한다. 가장 가까운 두 좌석의 거리는 (100 - 10) = 90 이다. 다른 예로, n = 6, s = 4 이고 x = [11, 19, 24, 26, 29, 30]이라 하자. 이 경우, x[1] = 11, x[2] = 19, x[3] = 24, x[4] = 29 각각에 좌석을 설치하면 가장 가까운 두 좌석의 거리는 5가 된다. 혹은, x[1] = 11, x[2] = 19, x[3] = 24, x[4] = 30을 선택하는 것도 가능하다. 가장 가까운 두 좌석의 거리가 6 이상이 되도록 4개의 좌석을 설치하는 방법은 없다.
입력으로 n, s, 그리고 x[1], ..., x[n]이 주어지면 가능한 가장 큰 D값을 출력하는 프로그램을 작성하시오.
import sys
input = lambda: sys.stdin.readline().strip()
def check(mini):
left = arr[0]
count = 0
for right in arr[1:]:
if right - left >= mini:
count += 1
left = right
if count >= (s - 1):
return True
return False
t = int(input())
for _ in range(t):
n, s = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
start, end = 0, arr[n - 1]
d = 0
while start <= end:
mid = (start + end) // 2
if check(mid):
d = max(d, mid)
start = mid + 1
else:
end = mid - 1
print(d)풀이
- D의 값 : mid
- 두 좌석을 골라 거리의 차가 mid 이상인 경우가 나오도록 반복해 그 경우의 수를 s와 비교해 최대 D값을 구한다.
