%2021. 11. 10. 01:32에 작성된 글입니다%
https://www.acmicpc.net/problem/10436
10436번: 무한 유리수 트리
무한 유리수 트리는 완전 이진 트리이며, 다음과 같이 정의된다. 루트는 1/1이다. p/q의 왼쪽 자식은 p/(p+q)이다. p/q의 오른쪽 자식은 (p+q)/q이다. 트리의 첫 세 층은 아래와 같이 구성된다. 이 무한
www.acmicpc.net
루트까지 올라갔다 내려와서 편하게 해결 보려는 생각은 꿈도 꾸지 말자. \(O(N)\)이라도 범위가 2147483647인지라...
주어진 값에서 바로 해결을 봐야 한다. 대단한 알고리즘은 없고 그냥 어디 종이 가지고 와서 트리 죽 적어본 뒤에 규칙을 찾으면 된다.
대부분의 경우에 간단하게 해결이 되고, 주어진 게 부모의 오른쪽 자식인 경우에 문제가 되는데... 이건 어쩔 수 없이 한 번 공통 조상까지 올라갔다 내려와야 한다.
물론 \(p\)와 \(q\)를 관찰하다 보면 쓸만한 방법을 금방 찾아낼 수 있다.