징검다리

• 제자리 멀리뛰기와 동일한 문제이다.
• 파라메트릭 서치로 푸는 문제.
• “제거할 돌의 갯수가 n일때의 거리의 최솟값 중 최댓값=x를 구하라” 가 원래 문제인데, 이걸 파라메트릭 서치 형태로 바꾸기 위해서 f(x)를 “거리의 최솟값이 x일때 제거할 돌의 최소 갯수” 또는 “모든 거리를 x보다 크게 만들기 위해 제거해야 하는 돌의 최소갯수” 라고 정의한다. 그러면 x가 커질수록 f(x)도 커진다. 이제 풀어야 하는 문제는 “f(x) ≤ n 인 x의 최댓값을 [1, 1,000,000,000] 범위 안에서 구하라”가 된다
  • n이 픽스된 상황에서 x의 범위를 구하는 문제를, 결정 문제로 바꾸는 과정에서는 x가 픽스된 상황에서 n의 범위를 체크하는 문제가 되다 보니 조금 헷갈리긴 한다.
• f(x) 를 구하는 것은, 앞에서부터 이전 돌의 위치부터 현재 돌의 거리가 x보다 작으면 현재 돌을 제거하는 방식으로 그리디하게 O(m)에 구할 수 있다 (m은 돌의 갯수)
• 이분탐색 구간의 상한은, distance / {남은돌의 갯수} 이다.
• 따라서 총 시간 복잡도는 O(mlogn)이 된다 (n=distance)

"""Solution code for "Programmers 43236. 징검다리".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43236
- Solution link: http://www.teferi.net/ps/problems/programmers/43236
"""

from teflib import binsearch


def solution(distance, rocks, n):

    def is_valid(min_dist):
        prev_rock = 0
        removed_rock_count = 0
        for rock in rocks:
            if rock - prev_rock >= min_dist:
                prev_rock = rock
            else:
                removed_rock_count += 1
        if distance - prev_rock < min_dist:
            removed_rock_count += 1
        return removed_rock_count <= n

    rocks.sort()
    beg, end = 0, distance // (len(rocks) - n + 1) + 1
    return binsearch.maximum_valid_integer(beg, end, is_valid)

• Dependency: teflib.binsearch.maximum_valid_integer