레이스
세준이는 세준항공으로 돈을 무지막지하게 번 뒤, 레이스 대회를 개최했다. 레이스 트랙은 길이가 N인 직선이다.
세준이는 심판 M명을 적절한 곳에 배치시키려고 한다. 심판은 아무 곳에나 배치시킬 수 있지 않다. 심판은 미리 정해진 K개의 곳에만 위치할 수 있다.
세준이는 심판을 배치할 때, 가장 가까운 두 심판의 거리를 최대로 하려고 한다.
심판을 어디에 배치시켜야 할지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같은 자연수이다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어진다. K개의 위치는 N보다 작거나 같은 자연수 또는 0이며, 오름차순으로 주어진다.
출력
첫째 줄에 심판을 어떻게 배치시켜야 가장 가까운 심판의 거리가 최대가 될 것이지 출력한다. 출력할 때는 예제와 같이 심판을 세울 곳에는 1을, 세우지 않을 곳에는 0을 출력한다. 만약 정답이 여러개일 경우에는 사전순으로 가장 늦는 것을 출력한다.
풀이
일단 문제를 읽어본 후에 문제처럼 구현하려면 굉장히 힘듭니다. 그래서 문제에서의 행위를 조금 바꿔서 생각하겠습니다.
먼저 심판의 최대거리를 찾아서 그 거리만큼 심판을 배치시키면서 심판의 수가 m과 같은지 확인하는 방식으로 문제를 해결하겠습니다.
최대거리를 빠르게 찾기 위해서는 이진탐색 알고리즘을 사용해야합니다. 시작값은 1이고, 마지막값은 위치의 초기값과 마지막값의 거리이겠죠. 그 안에서 최대거리가 결정될테니까요.
이후에 심판을 세워보면서 심판의 수가 적다면 거리를 줄여야하고, 심판의 수가 같거나 크다면, 거리를 키워야할 것입니다.
그리고 해당조건을 확인하면 무조건 맨 처음의 위치에는 심판을 세워야 사전순으로 가장 늦는 값을 결과로 출력할 수 있겠죠.
이렇게 거리가 구해진다면, 결과문자열을 생성해서 출력하면 됩니다. 코드를 보겠습니다.
import sys
input = sys.stdin.readline
# n, m, k값 입력받기
n, m, k = map(int, input().split())
# 심판이 설 수 있는 위치입력
position = list(map(int, input().split()))
# 심판은 최소 1만큼 떨어져있음.
start = 1
# 심판은 최대 위치의 시작과 끝만큼 떨어져있음.
end = position[-1] - position[0]
# 최대거리 탐색 시작
while start <= end:
mid = (start + end) // 2
cnt = 1 # 심판의 수 -> 처음자리는 무조건 심판이 섬.
prev = position[0] # 이전값 저장 변수
for i in range(1, k):
# 위치가 최대거리보다 같거나 크면 심판이 설 수 있음.
if position[i] - prev >= mid:
cnt += 1 # 심판수 증가
prev = position[i] # 이전값 갱신
# 심판의 수가 적다면 거리는 작아져야함.
if cnt < m:
end = mid - 1
# 심판의 수가 크다면 result에 저장하고
# 거리를 늘려봄.
else:
result = mid
start = mid + 1
# 처음엔 무조건 심판이 서있음.
# 이진탐색에서 심판수 확인 로직과 동일.
ans = '1'
cnt = 1
prev = position[0]
for i in range(1, k):
# 심판의 수가 m을 넘지 않으면 심판을 세움.
if position[i] - prev >= result and cnt < m:
ans += '1'
cnt += 1
prev = position[i]
else:
ans += '0'
# 결과출력
print(ans)
