[백준 1508번] 레이스 (Python3)

import sys
input = sys.stdin.readline
from bisect import bisect_left

def calmin():
  MIN = N+1
  for i in range(1,M):
    if MIN > location[where[i]]-location[where[i-1]]:
      MIN = location[where[i]]-location[where[i-1]]
      idx = i
  return idx,MIN

def relocation():
  global where
  idx,MIN = calmin()
  newwhere = where[:]
  for i in range(idx,M):
    new = bisect_left(location,location[newwhere[i-1]]+MIN+1)
    if new >= K:
      return False
    newwhere[i] = new
  where = newwhere
  return True

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

location = [*map(int,input().split())]
where = [i for i in range(M)]
while relocation():
  continue

check = [0]*K
for i in where:
  check[i] = 1
print("".join(map(str,check)))

처음 문제를 읽고 해결방법을 찾기 힘들었다. 내가 생각한 그리디한 방식이 잘 통하지 않았기 때문이다.

그러다가 이 문제가 "매개 변수 탐색" 이라는 알고리즘으로 해결하는 문제라는 것을 알게되었다.

그래서 매개 변수 탐색에 대해서 대충 훑어보니 기준값을 잡고 기준값보다 큰 최솟값을 찾아나가는 알고리즘이라는 것을 알게되었다. 그러니까 풀이법이 바로 생각났다.

 

알고리즘을 요약하면 이러하다.

1. 일단 시작은 모든 심판을 왼쪽부터 차례로 배치시킨다.

2. calmin 함수로 간격이 가장 좁은 두 심판을 찾고, 그 간격의 크기(MIN)와 이때의 오른쪽의 심판(idx)을 출력한다.

3. relocation 함수로 calmin으로 찾은 심판부터 모든 심판들을 (이전 심판의 위치 + MIN)보다 더 멀리 배치한다. (이분탐색을 활용하면 빠르다)

4. relocation 함수로 심판을 배치할 수 없으면 이때의 심판의 위치를 출력한다.

 

 

오늘의 교훈) 매개 변수 탐색을 염두하자