[2019 카카오 기출] 징검다리 건너기

 

<출처: https://programmers.co.kr/learn/courses/30/lessons/64062>

---

스톤 배열 크기를 N이라 했을 때

정렬을 수행하고 선형탐색을 통해 건너려고 하면 O(N^2)이 되어 시간초과가 나게 됩니다.

결국 특정 높이에 대한 탐색을 O(N)이 아닌, O(logN)에 해야하므로 이분 탐색으로 접근해볼수 있습니다.

 

통과한 니니즈 친구들의 수를 F라고 했을 때, 각 돌은 F만큼 높이가 감소합니다.

이 감소한 높이로 인해 연속으로 0이 되는 돌의 개수가 K이상이면 더 이상 친구들은 지나갈 수 없습니다.

 

그래서 특정 인원 수 M명이 지나간 후에 디딤돌을 더 지날 수 있는지 없는지를 파악해서

이 M값의 상한선을 구하면 그게 답이 됩니다.  

---

<코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/kakao23_0505.cc>