징검다리 건너기

programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

처음에 이 문제를 접근할 때 DP로 생각했었다. 왜냐하면 K개 이상의 연속된 돌 중에서 가장 큰 값이 건널 수 있는 인원 수이기 때문이다.

K개의 돌 중에서 가장 값이 큰걸 기준으로 DP배열에 기록해두고, 이후에 진행할 때는 덱을 사용하여 먼저 넣었던 원소를 빼고, 그 다음 원소를 추가 및 최댓값을 갱신하여 다시 DP 배열에 기록하는 방식이다.

그런데 정확성은 모두 통과했지만 효율성을 통과하지 못했다. 의심되는 원인으로는 최댓값을 구하기 위한 방법으로 max_element를 K개의 범위에서 돌렸는데 이게 원인인걸로 의심된다.

그래서 다른 코드를 참고한 결과 이분 탐색을 사용하여 접근한 아이디어를 보았다.

핵심은 다음과 같다.

1. 가장 큰 돌의 값을 구한다.

2. 가장 작은 값 (0) 과 mid를 구한다.

    2.1 mid보다 작은 값의 돌들을 카운트하여 K개보다 같거나 크다면 건널 수 없으므로 범위를 줄인다.

3. 발견된 값 중에 가장 큰 돌의 값을 갱신한다.

 

고찰

이분 탐색은 정렬된 배열에서 먹힐만한 테크닉이라 생각했었는데, 결정문제로 바꾸는 과정이 미숙했었던 것 같다.