징검다리

두 문제를 합쳐놓은 문제다. 대충설명 할꺼니까 위에 두 문제 모르면 공부ㄱ

import math
def solution(distance, rocks, n):
    rocks.sort()
    min_, max_ = 1, distance
    while min_ < max_ :
        destroy = 0; piv_rock = 0
        estimate_min_distance = (min_+max_) // 2 
        for rock in rocks :
            if rock - piv_rock < estimate_min_distance : destroy += 1
            else : piv_rock = rock
        if destroy > n : max_ = estimate_min_distance
        else : min_ = estimate_min_distance + 1
    return min_ - 1

알고리즘

추정값 = 돌사이 깼을 때 나올 수 있는 최소거리

1 <= 추정값 <= distances

돌 사이의 거리가 추정값보다 작지 않도록 바위를 다부심

부순 돌의 갯수가 n을 넘어가면 최대값줄이고, 아니라면 최소값 높여서 BinarySearch

징검다리

알고리즘

Comments