[Python] 프로그래머스. 징검다리 (Level 4)

https://programmers.co.kr/learn/courses/30/lessons/43236

코딩테스트 연습 - 징검다리 | 프로그래머스

이분탐색 문제.

distance 제한사항이 1,000,000,000인 것에서 이분탐색 느낌이 강하게 오긴 했지만,

이분탐색에서 기준으로 삼을 값이 뭔지 도저히 감이 안 와서 다른 블로그 해설을 참고해야만 했다.

 

이분탐색의 기준은 '돌과 돌 사이의 거리' 였고, 이분탐색을 진행하는 방법은

1. '돌과 돌 사이의 거리가 이분탐색 기준값보다 작을 경우 뒤쪽 돌을 삭제한다'

2. 삭제한 돌의 개수가 기준 n보다 클 경우 돌과 돌 사이의 거리를 줄이고, n보다 작거나 같을 경우 거리를 늘리는 식으로 이분탐색을 진행한다.

 

'무엇을 이분탐색 값으로 설정할 것인지', '이분탐색의 left, right값을 변화시킬 기준은 무엇인지' 익숙해지는 게 왜 이리 어려운지 모르겠다.