백준 1508: 레이스(python)

문제

---

풀이

 

배치된 심판들 사이에서 가장 가까운 두 심판의 거리를 최대로 만드는 것, 즉 min gap을 최대화하는 문제이다. 이분 탐색 + 그리디로 풀이할 수 있다. 후보 거리 d에 대해 d만큼의 간격을 두고 심판을 M명 배치할 수 있는지 greedy하게 검증하며, 이를 코드로 나타내면 다음과 같다.

s = 1   # 최소 거리: 1
e = position[-1] - position[0]    # 최대 거리: 끝에서 끝까지

while s <= e:   # 이분 탐색=
    mid = (s + e) // 2
    cnt = 1  # 처음에는 무조건 심판
    prev = position[0]  # 직전에 심판이 배치된 위치
    for i in range(1, K):
        if position[i] - prev >= mid:   # 이전 심판으로부터 거리가 mid 이상인 경우에만 배치
            cnt += 1    # 배치한 심판 수 1 증가하고
            prev = position[i]  # 직전 위치 갱신

    if cnt < M: # 심판을 다 세우지 못하면 거리를 더 줄여야 함
        e = mid - 1
    else:       # 심판을 다 세울 수 있으면 거리를 한 번 더 늘려 봄
        result = mid
        s = mid + 1

구간 양 끝 포인터인 s와 e를 설정하고 범위를 조정하며 탐색하는 것은 일반적인 이분 탐색 과정과 동일하다. s와 e의 중간 지점인 mid가 현재 검증할 거리가 되며, 일단 가장 왼쪽에 심판을 배치한 다음 for문 순회하며 바로 이전에 배치된 심판으로부터 mid 이상 떨어진 경우에만 심판을 배치한다. cnt가 1 증가하면 심판이 한명 더 배치된 것이 되며, for문이 종료된 다음 배치된 심판 수가 M보다 작을 경우 심판을 다 세우지 못한 것이므로 e를 mid-1로 변경해 간격을 줄이고, cnt가 M 이상이면 간격을 늘려 한번 더 테스트하기 위해 s를 mid+1로 변경한다.

 

이분 탐색이 종료된 후, 조건을 만족하면서 가장 크게 유지할 수 있었던 d가 답이 된다. 최소 간격을 d로 두고 실제로 어떤 위치에 심판을 배치할지는 다시 한 번 아래와 같이 greedy하게 결정한다.

res = '1'
cnt = 1
prev = position[0]
for i in range(1, K):
    if position[i] - prev >= result and cnt < M:
        res += '1'
        cnt += 1
        prev = position[i]
    else:
        res += '0'

 

---

전체 코드

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
position = list(map(int, input().split()))

s = 1   # 최소 거리: 1
e = position[-1] - position[0]    # 최대 거리: 끝에서 끝까지

while s <= e:   # 이분 탐색
    mid = (s + e) // 2
    cnt = 1  # 처음에는 무조건 심판
    prev = position[0]  # 직전에 심판이 배치된 위치
    for i in range(1, K):
        if position[i] - prev >= mid:   # 이전 심판으로부터 거리가 mid 이상인 경우에만 배치
            cnt += 1    # 배치한 심판 수 1 증가하고
            prev = position[i]  # 직전 위치 갱신

    if cnt < M: # 심판을 다 세우지 못하면 거리를 더 줄여야 함
        e = mid - 1
    else:       # 심판을 다 세울 수 있으면 거리를 한 번 더 늘려 봄
        result = mid
        s = mid + 1

res = '1'
cnt = 1
prev = position[0]
for i in range(1, K):
    if position[i] - prev >= result and cnt < M:
        res += '1'
        cnt += 1
        prev = position[i]
    else:
        res += '0'

print(res)