징검다리

송지용·2019년 5월 14일

algorithm

목록 보기

35/50

flow
일단 카테고리도 그렇고 바로 이분탐색 솔루션이 떠올랐다. 거리의 최솟값을 타겟으로 이분탐색을 진행하는데 검증하는 방법에는 greedy 한 방법을 쓰면 된다. 정렬된 rocks 를 순서대로 보면서 이전 바위와의 거리가 설정된 거리값인 mid 보다 작다면 그냥 치워버리면 된다. 만약 안치운다면? 앞에 있는 바위를 치워야 하고 이는 똑같은 값이거나 오히려 다음 바위까지의 거리가 가까워지면서 더 안좋은 결과를 만들게 된다.. 작은 인덱스부터 순서대로 나아가기 때문에 부분해가 전체해가 되는 greedy 가 통한다.
시간복잡도는 O(R x log D), R: 바위갯수, D: 총 거리
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A2.py