burning-carrot / study-problem-solving

알고리즘 고수가 되기 위한 지름길

5 stars 1 forks source link

junow programmers 43236 징검다리 #106

Closed Junow closed 4 years ago

Junow commented 4 years ago

43236. 징검다리

난이도	정답률(_%)

메모리 (KB)	시간 (ms)

설계

이분탐색 대상을 정한다.

여기서는 답으로 바위사이의 "최소" 중 "최대" 를 찾아줘야함. (이게 젤 어렵)
m 값을 각 차이값들의 "최소" 라고 가정했을때 이 값보다 작은 애들을 모두 제거해줌. (그래야 m 이 최소가 되니까)
- 지운 바위수가 n 보다 크면 줄여야함 (너무 많이 제거됐기 때문)
- 지운 바위수가 n 보다 작으면 늘려야함 (덜 제거됐기 때문, 여유있는 상태)
- 이때 정답이 갱신됨, 더 제거할 수 있기 때문에 (이전 보다 더 큰 수가 들어옴)

시간복잡도

O(NlogN) ??