📚 1508 - 레이스

레이스

이해

K개의 위치는 N보다 작거나 같은 자연수이다.

이분 탐색을 통해 구현한다.

prev = 0
for i in range(1, k):  
    # 인덱스를 돌아보며, 중앙 값보다 큰 값을 거리로 가질 때  
    if position[i] - position[prev] >= mid:  
        cur += "1"  # 1 추가
        selected += 1  # 심판 인원 수 추가
        prev = i  
  
        if selected == m:  
            break  
    else:  
        cur += "0"

• mid는 (0 + N) // 2로 구한다.
• 이전 prev위치와 현재 i번째 위치에 저장되어 있는 값들의 차이를 구한다.
• 만약 mid보다 크거나 같다면, 1을 추가하고 기준 값 업데이트
• 심판을 다 구했다면 종료

if selected == m:  
    start = mid + 1  
    res = cur  
else:  
    end = mid - 1

• 심판 위치를 다 찾았다면, 이분 탐색에서 다음 start는 mid + 1 이다.
• 심판 위치를 다 찾았을 경우, res는 현재 나온 결과를 저장한다.
• 문제에서 만약 정답이 여러개 일 경우, 사전순으로 가장 늦는 것을 출력하라고 했으므로, 새로운 게 추가될 때마다 삽입하면 된다.

소스

import sys

read = sys.stdin.readline

n, m, k = map(int, read().split())

position = list(map(int, read().split()))


# 이분 탐색
def solution():
    # 결과 값
    res = 0

    # 시작은 0으로
    start = 0

    # end는 레이스 트랙
    end = n

    # start가 end보다 작거나 같을 때 (이분 탐색)
    while start <= end:
        mid = (start + end) // 2

        cur = "1"
        selected = 1
        prev = 0

        for i in range(1, k):
            # 인덱스를 돌아보며, 중앙 값보다 큰 값을 거리로 가질 때
            if position[i] - position[prev] >= mid:
                # print(position[i], position[prev], mid)
                cur += "1"
                selected += 1
                prev = i

                # 심판 명수 다 구했을 때 종료
                if selected == m:
                    break
            else:
                cur += "0"

        # 가득 채워지지 않았다면 나간다.
        while len(cur) < k:
            cur += '0'

        # 심판 위치를 다 찾았을 때
        # 이분 탐색에서 (왼쪽, 오른쪽이 있을 때) 오른쪽으로
        # 심판을 선택할 때 앞부터 진행, 문제에서 가장 마지막에 갱신된 cur을 결과로 출력한다.
        if selected == m:
            start = mid + 1
            res = cur
        else:
            end = mid - 1
        # print("res : ", res)

    print(res)

solution()