https://www.codingame.com/training/medium/rational-number-tree
접근법
- LRLR은 직접 해보면 됨 : 왼쪽, 중간, 가운데 적절히 교체하면서
- 수를 찾는 부분은 이진탐색 사용
- 백준에 비슷한 문제가 생각나서 분수의 특징을 찾는 것인가 했는데..
- 신기하게도 진짜 "사이값"임 : 새로 생성되는 분수의 크기는 두 분수의 사이에 있음
- 이를 이용해서 찾는 값이 왼쪽인지? 오른쪽인지 찾아갈 수 있음
newbieski