이 문제는 처음에 직접 트리를 생성하려고 했고 실제로 로직상은 맞은 것 같아 보였다.
그러나 문제는 2의 30 제곱이 1억이 넘기 때문에 메모리 초과가 났다.
사실 이 조건을 주의깊게 보지 않았기에 당황했다.
[풀이]
트리에서 부모 자식 간의 관계는
왼쪽이 부모자리 * 2, 오른쪽이 부모자리 * 2 + 1을 생각해보자
근데 그렇게 한다고 해도 딱히 뭔가 생각은 나지 않았다.
그러나. 2 의 (height + 1) 제곱에서 해당 자리를 빼면 원하는 정답이 나온다.
출처: KTH Challenge 2014
단순한 변형 아이디어인데 참신하다고 생각했다.