[백준]1508 - 레이스 (#파이썬 #그리디 #이분탐색 #경계 설정 후 카운팅)

 

1508번: 레이스

문제를 간단하게 표현하면 가장 가까운 심판 간 거리가 최대가 되도록 배치하는 문제이다. 최대한 듬성듬성 배치하는 것이다. 최대한 '듬성듬성' 배치하기 위해 '심판 간 거리에 대해 그리디 전략'을 취할 수 있다. 심판의 거리를 최대한 넓혀서 배치해 보고, 문제 조건에 맞지 않으면 좁혀서 배치해 보고, 또다시 넓혀 보고, ... 반복하며 정답을 찾을 수 있다. 즉, 이분탐색으로 경계(심판 간 최대 거리)를 설정한 후에 해당 경계에서 몇 명의 심판을 배치할 수 있는지 배치해보는 것이다.

심판 배치 로직

출력할 때는 예제와 같이 심판을 세울 곳에는 1을, 세우지 않을 곳에는 0을 출력한다. 만약 정답이 여러개일 경우에는 사전순으로 가장 늦는 것을 출력한다.

문제의 출력 조건을 살펴보면 '사전순으로 가장 늦는 것을 출력한다'는 조건이 있다. 이를 통해 알 수 있는 것은 심판의 위치가 작은 것부터 배치를 하고, 문제의 조건에 부합한다면 해당 배치가 정답이 된다는 것이다.

가령 심판의 위치가 0, 5, 10, 15이고, 경계(= 최대 떨어진 거리)를 5라고 가정하면 '1110', '0111' 배치 모두 가능하다. 그런데, 출력 조건에서 사전순으로 가장 늦는 것을 출력한다는 조건에 의해 '1110'이 정답이 되는 것이다. 심판의 위치가 작은 것부터 배치하면 되는 것임을 판단할 수 있다.

심판 배치 시작은 어디서부터?

나는 심판 배치의 시작 위치를 모든 케이스에 대해 모두 검증해주었다. 왜냐하면 K 값이 최대 50으로 충분히 작아 모든 케이스에 대해 검증하더라도 시간 복잡도가 O(2500) 수준으로 매우 작기 때문이다.

아래의 코드를 보면, st 인덱스에는 무조건 심판이 배치되고, 해당 인덱스보다 위치 값이 큰 곳에만 심판이 배치되는 것을 알 수 있다.

for st in range(K):
        # st 인덱스에는 무조건 심판 배치
        order = ''
        cnt = 1
        for _ in range(st): order += '0'
        order += '1'
        prev = st
        
        for i in range(st + 1, K):
            if cnt == M:
                order += '0'
                continue
            if seq[i] - seq[prev] >= gap:
                prev = i
                order += '1'
                cnt += 1
            else:
                order += '0'

st 인덱스 전에는 심판이 배치되지 않으며(= for _ in range(st): order += '0'), 해당 위치 이후부터 순회한다(= for i in range(st + 1, K):).

심판 배치의 끝은 언제?

위 코드 블럭의 cnt가 M이 되면 무조건 order += '0' 처리되는 부분으로 심판 배치가 끝난 경우에 대해 처리하였다. 즉, 심판 배치 개수인 cnt가 M으로 문제 조건에 부합하게 배치가 끝났다면 뒤에는 더 이상 심판을 배치하지 않는 것이다. 이렇게 처리할 수 있는 이유는 정답이 여러 개인 경우 '사전순으로 가장 늦은 것을 출력한다'는 조건이 있기 때문이다. cnt가 M개 만큼 배치하지 못하는 경우에는 문제 조건을 만족하지 못하는 경우이므로 이분탐색에서 조건 조정이 이루어진다.

이분 탐색에서 경계 조정

l = 1
r = N
while l <= r:
    length = (l + r) // 2
    refCnt, refOrder = refreeCount(length)
    if refCnt > M:
        l = length + 1
    elif refCnt < M:
        r = length - 1
    else:
        ans = refOrder
        l = length + 1

print(ans)

초기 l과 r은 각각 1, N으로 설정된다. 이 l, r을 통해 경계(length)를 설정하여 해당 경계를 바탕으로 심판 배치 수, 심판 배치 결과(refCnt, refOrder)를 반환받는다.

심판 배치 수가 문제 조건보다 큰 경우 경계를 늘려서 심판 배치가 더 적게 되도록 조정한다. 심판 배치수가 문제 조건보다 작은 경우 경계를 줄여서 심판 배치가 더 많게 되도록 조정한다. 문제 조건과 맞게 심판이 배치된 경우 ans 값에 심판 배치 결과를 할당하고, 경계가 더 커졌을 때도 정답을 찾을 수는 없을지 확인할 수 있도록 조정(l = length + 1)한다.

시간 복잡도(Time Complexity)

이분 탐색을 통해 경계를 설정하는 것의 시간 복잡도는 O(log(N))이다. 이분 탐색 내에서 심판을 배치하는 과정의 시간 복잡도를 계산해 보면 O(K^2)이다. K는 50 이하이므로 O(K^2 * log(N))은 충분히 계산 가능한 시간 복잡도임을 알 수 있다.

 

📁 코드 전문