https://www.acmicpc.net/problem/30871
문제요약
- 이해하기 힘든 함수가 주어지고
- 조건을 만족하는 x를 구하기
접근법
- 주어진 함수가 난해하기 때문에 자세하게 이해하려고 하지 않는 것은 알겠음
- 처음에 함수를 잘못 이해해서 잘못된 접근방법을 하였음
- 해설을 참고했으나 이해하는데 오래걸림(링크텍스트)
- 0일때와 10^18 + 1일때는 결과가 확실함
- 0 : 모든 수보다 작을 것이므로 조건을 만족하지 않아서 모두 건너뛰면 결국 초기값인 0만 남아서 함수의 결과는 false
- 10^18 + 1 : 모든 수 보다 크기 때문에 조건을 모두 만족하지 않아서 건너뛰면 결국 초기값인 10^18+1만 남아서 함수의 결과는 true
- 그럼 가장 작을때 false, 가장 클때 true이기 때문에 중간 어딘가에서 false->true가 되는 구간이 있다는 의미
- 하지만 계속 F,...,F,T,.....T 이런것을 의미하는 것은 아니고 어쨌든 중간 어딘가에서 f->t로 바뀌는 부분이 있다는 의미
- 그렇다면 잘은 모르겠지만 0 ~ 10^18+1의 중간값 m을 정해서 f(m)을 구해보면
- f(m)이 true인 경우 F .... T......T => 0~m사이에 바뀌는 구간이 있겠구나
- f(m)이 false인 경우 F.....F......T => m~10^18+1 사이에 바뀌는 구간이 있겠구나
- 함수가 연속적이진 않지만 어딘가 바뀌는 구간이 있는지를 찾아갈 수 있음!
- 굉장히 신기하고 기발한 이분탐색(parameter search)
newbieski