https://www.acmicpc.net/problem/22958
요약
- 인터렉티브 문제
- 수열에서 가장 큰 값의 위치를 찾는 것
- 쿼리를 사용할 수 있고, 쿼리 제한 조건이 있음
접근법
- 반씩 줄여나가는 접근법이 필요함
- 1부터 N까지 1간격 쿼리를 사용하면 최대값이 무엇인지 알 수 있음
- 1간격을 2간격 두개로 나눠서 한쪽에 최대값이 있는지 확인할 수 있음 ==> 어느쪽 2간격에 최대값이 있는지 확인 가능
- 2간격을 4간격 두개로 나눠서 어느쪽에 최대값이 있는지 확인 가능
- 최후의 하나가 남을때까지 반복
주의점
- 쿼리 횟수가 2N-1 이하여야하므로, 두개의 간격중 작은쪽으로 쿼리하기
- 사용하는 기기가 N 보다 작아야함 : x2를 하다가보면 범위를 넘어감
newbieski