카카오 개발자 겨울 인턴십

[프로그래머스 2019 카카오 개발자 겨울 인턴십] 징검다리 건너기 (파라매트릭 서치) [C++]

https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr n이 20만이고 각 배열의 최댓값(m)은 2억이다. 따라서 매번 모든 배열에 -1을 빼주면서 k개 이내의 돌다리를 건너는 게 가능한지 확인하는 방법은 시간 초과가 날 것이다. 따라서 파라매트릭 서치를 사용했다. 이분 탐색으로 몇 번째에 건너지 못하는지를 찾는 것이다. 그렇게 되면 건너는 게 가능한지 확인하는 O(n) * 적당한 값을 이분 탐색하는 logm이므로 O(nlogm)에 해결이 가능하다. #include #include #include using namespace st..