[백준] 1508번 레이스

https://www.acmicpc.net/problem/1508

1508번: 레이스

 

이런 류의 문제는 이분탐색을 써야겠다고 생각했지만 코드로 구현해내지 못했다.

import sys

N, M, K = map(int, sys.stdin.readline().split())
loc = list(map(int, sys.stdin.readline().split()))

start = 0
end = loc[-1] - loc[0]


def check(mid):
    now = -1
    cnt = 0
    for i in range(K):
        if now <= loc[i]:
            now = loc[i] + mid
            cnt += 1
    if cnt < M:
        return False
    return True


tmp = 0
while start <= end:
    mid = (start + end) // 2
    if check(mid):
        tmp = mid
        start = mid + 1
    else:
        end = mid - 1

answer = ""
now = 0
cnt = 0
for i in range(K):
    if now <= loc[i] and cnt < M:
        answer += "1"
        now = loc[i] + tmp
        cnt += 1
    else:
        answer += "0"
print(answer)

check함수

최소 mid의 간격을 갖도록 하면 사람들 몇 명을 배치할 수 있는가? 에 대한 함수이다.

현재 위치 now를 -1로 두고, 

for문을 돌면서 현재 위치를 방문하면서 아예 mid(간격)을 더해버린다.

그리고 계속 if문으로 now <= loc[i]를 검사하니까, loc는 정렬되어있으므로 mid간격 이상의 가장 가까운 지점들을 방문할 수 있는 것이다.

그렇게 구한 cnt가 배치해야 하는 사람 수보다 적으면 return False

 

이분탐색 코드

while start <= end 등호를 붙이려면

start, end에 mid 값 +1, -1을 해줘야 한다. 아니면 무한루프에 빠질 수 있다.

 

 

https://thought-process-ing.tistory.com/232

[python] 백준 1508 레이스