[Gold V] 사회적 거리 두기 - 20917

문제 링크

성능 요약

메모리: 57488 KB, 시간: 4568 ms

분류

이분 탐색, 매개 변수 탐색

문제 설명

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값을 출력하는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 줄에 걸쳐 주어진다.

첫 줄에 n과 s가 공백으로 구분되어 주어진다. 다음 줄에 설치된 콘센트의 위치를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해 달성 가능한 최대 D값을 출력한다.

---

풀이

아이디어

최대 거리를 lst[0] 과 lst[-1] 사이의 거리를 기준으로 mid를 구했을 때, 꼽을 수 있는 콘센트의 개수가 s 보다 크거나 같으면 upper_bound로 탐색범위를 재 설정하고, 작으면 lower_bound로 탐색 범위를 설정하여, mid 값이 최대가 될 때 그것을 정답으로 맞추는 문제였다.

조금 더 직관적으로 설명하자면 n=6, s=4 이며, x=[11, 19, 24, 26, 29, 30]일때 d의 값을 구하는 문제인데 탐색 과정은 아래와 같다.

• 초기 상태

start = 0, end = 30
mid = 15

left= 11, right=[19, 24,26,29,30]일때 right - left > mid인 경우 콘센트를 꼽을 수 있는 경우로 판단하고, cnt를 1 증가 시켜 준 뒤 left=right로 하여, 콘센트가 꼽힌 부분부터 다시 탐색해 나가는 방식이다.
그러나 초기 상태의 경우 선택할 수 있는 경우의 수가 s보다 작으므로 end = mid - 1로 lower_bound 탐색 해준다.

• 두번째

start = 0, end = 14
mid = 7

left= 11, right=[19, 24,26,29,30]는 동일하며, 아래 과정을 따른다

1. 
left = 11, right = [19, 24, 26, 29, 30]
일때, 19가 조건에 만족

cnt = 1
left = 19

2.
left = 19 right = [24, 26, 29, 30]
일때, 26이 조건에 만족

cnt = 2
left = 26

더이상 만족하는 경우 없음.
cnt = 2, s = 4

s > cnt + 1 이므로 lower_bound 탐색

• 세번째

start = 0, end = 7
mid = 3

1.
left = 11, right = [19, 24, 26, 29, 30]
일때, 19가 조건 만족

cnt = 1
left = 19

2.
left = 19 right = [24, 26, 29, 30]
일 때, 24가 조건 만족

cnt = 2
left = 24

3.
left = 24 right = [26, 29, 30]
일 때 29가 조건 만족

cnt = 3
left = 29

더이상 만족하는 경우 없음
cnt = 3, s = 4

s == cnt + 1 이므로, upper_bound 탐색

• 네번째

start = 4, end = 7
mid = 5

1.
left = 11, right = [19, 24, 26, 29, 30]
일때, 19가 조건 만족

cnt = 1
left = 19

2.
left = 19 right = [24, 26, 29, 30]
일 때, 24가 조건 만족

cnt = 2
left = 24

3.
left = 24 right = [26, 29, 30]
일 때 29가 조건 만족

이때, cnt 의 크기는 mid=3일때와 동일하지만, mid=5일때 더 크므로 d=5여야 한다.
이후 과정은
left=6, right=7 -> upper_bound
left=6, right=6 -> lower_bound *반복문 종료
즉 d=5이다.

코드

import sys
input = sys.stdin.readline

def check(dist, m, s):
    cnt = 1
    left = dist[0]
    for right in dist[1:]:
        if right - left >= m:
            cnt += 1
            left = right
    return cnt >= s

def solve():
    _, s = map(int, input().split())
    lst = list(map(int, input().split()))
    lst.sort()

    left, right = 0, lst[-1]
    d = 0
    while left <= right:
        mid = (left + right) // 2
        if check(lst, mid, s):  # 콘센트를 꼽은 수가 많은 경우
            left = mid + 1
            d = max(d, mid)

        else:
            right = mid - 1
            
    print(d)

    
if __name__ == "__main__":
    for i in range(int(input())):
        solve()

---

회고

아이디어를 떠올리는데 정말 미친듯이 어려웠다.
결국 다른 사람의 아이디어를 참고 했는데, 참고했는데도 어려웠다.
그래도 손으로 직접 풀어나가면서 이해하는데는 성공했으며 한층 더 성장했음에 믿어 의심치 않는다.