DARPA Grand Challenge

문제: DARPA / 동적계획법, 이진탐색

처음에 greedy로 접근했다가 몇 번 물먹은 문제다.

잊고 지내다가 알고리즘 책(프로그래밍 콘테스트 챌린징)에서 유사한 문제를 보고 다시 도전해서 성공했다.

핵심전략은 다음과 같다.

모든 카메라에 대해, 임의의 두 카메라 간격을 d로 만들 수 있는지 확인한다.

1. d값은 입력으로 주어진 간격의 최대 값부터 시작한다.

2. 만약 모든 카메라를 d간격 이상으로 설치할 수 있다면 d값을 늘려서 시도해본다. 왜? 가장 가까운 카메라 간격을 최대화 시켜야 하니까.

3. 만약 실패하면 d값을 줄여서 시도해본다. 

이렇게  d값을 조절해가면서 범위를 좁혀나간다. 2, 3번 과정에 이진탐색이 적용된다. 

2번일 경우 left 값을 mid값으로 한다. 3번일 경우 right 값을 mid값으로 하면된다.

언제까지? 오차가 허용되는 범위까지.

코드: https://github.com/xgate/algospot/blob/master/SEARCH/DARPA.cpp