https://www.acmicpc.net/problem/22901
요약
- 2100 ~ 2399 사이 숫자를 "y 이상인가?" 쿼리를 통해 맞춘다.
- 최대 1회에 한해 잘못된 답변이 나옴 : y 미만인데 y 이상이라고 답함
- 쿼리 회수 18, 14, 13 차등 배점
접근법
- 이분탐색을 해야하는 것은 알겠는데 틀린 답변 해결책이 어려움
- 0인경우에 1로 잘못된 답변을 하는 경우가 최대 한번 존재함
- 1 -> 0은 없다는 것
- 최대 한번인 것에 집중
- 쿼리를 두번씩 던지면 정답의 보정은 될 것 같으나 최대 18회 쿼리 필요
관찰
- 이분탐색으로 진행할때 관찰을 해본다
- 응답이 0이 나왔다? 맞는말
- 응답이 1이 나왔다? 의심
- 다음 응답이 0이 나왔다? => 앞의 응답을 다시 물어봐야함
- 다음 응답이 1이 나왔다?
- 앞의 응답이 거짓, 다음 응답이 거짓 => 발생 안함(최대 1번 거짓)
- 앞의 응답이 참, 다음 응답이 참 => 가능
- 앞의 응답이 참, 다음 응답이 거짓 => 가능
- 앞의 응답이 거짓, 다음 응답이 참 => 발생할 수 없음, 거짓 결과로 인해 다음 응답은 오른쪽 구간에 대한 질문이고 1이 나왔다는 것은 오른쪽의 오른쪽이라는 의미. 하지만 실제 값은 왼쪽 범위에 속해야함(앞의 응답이 거짓이므로 진짜는 0이라는 의미이고 이는 왼쪽 범위라는 의미). 따라서 말이 안됨
- 정리해보면 1이 나온경우 일단 의심을 하는데
- (1, 0) => 1을 의심
- (1, 1) => 앞의 1은 참
구현
- 관찰을 결과로 구현으로 들어감
- 앞에 나온 결과와 범위를 들고 다님
- 앞에 나온 결과가 거짓인 경우 roll back수행
- 어려웠던 부분은 엣지 케이스에서 수행 횟수가 13을 넘는 경우였음
- 4개, 5개가 남았을 경우 시뮬레이션을 해보면 됨
- 결국 손으로 일일이 구현은 했지만, 더 깔끔한 로직이면 가볍게 회피 가능했을 것임
newbieski