백준 3652, 새트리

개요

문제 링크
골드 5, 재귀
모든 유리수를 커버하는 이진트리의 노드 위치 찾기

---

접근

1. 식은 어려우니 보지말고, 트리의 그림을 잘 보고 규칙성을 판단해보자. 오른쪽 트리는 분자가 크고, 왼쪽 트리는 분모가 크다. 그리고 분자와 분모가 같은 경우는 루트노드 뿐이다.

2. 그러면 분자가 크다면 오른쪽으로, 분모가 크다면 왼쪽으로 간 것인가? 하는 느낌을 받을 수 있다.

3. 그럼 while문을 쓰면서, 분모와 분자가 같으면 멈추고, 분자가 클 때와 분모가 클 때 서로 다른 변형을 주면 되지 않을까? 그게 됐다.
   만약 분자가 크다면 R을, 분모가 크다면 L을 string에 넣어준다. 그리고 다음 행선지는 각각 {u,d}={d-u,u},{d,u-d}로 찍어주니 맞았다.

4. 왜 될까? 천천히 식을 뜯어보자. 2/1의 left subtree를 잘 보자. 2/1의 left subtree는 1/1의 left subtree의 복사본인데, 모두 분수를 뒤집고 1을 추가한 형태이다. 왼쪽은 항상 분모가 크므로, (U,D) -> (U+D,U)의 시행을 하면 항상 분자가 커지게 된다.

   

   이때 대응되는 1/4와 5/1을 보자. 1/4를 가기 위한 루트 root = LRL, 5/1을 가기위한 루트는 RLRL = R+root이다. 그리고 둘은 (U,D)->(U+D,U)의 시행의 차이가 있다.
   즉 분자가 큰 오른쪽 subtree에 존재하는 점은, R의 시행을 맨 앞에 추가해주어야 하고, (U,D)->(U+D,U)의 시행을 거쳐야 한다는 뜻이다.

5. (U,D)->(U+D,U)의 역변환을 생각하면 (U,D)->(D,U-D)이다. 이 역변환을 통해 5/1은 1/4가 된다. 1/4는 다시 깊이가 3인 트리의 복사본이고, 3/1과 대응된다. 3/1의 경로는 RL, 1/4의 경로는 LRL = L+RL이므로, 분모가 큰 왼쪽 subtree에 존재하는 점은 L의 시행을 맨 앞에 추가해주어야 하고 (U,D)->(D,U+D)의 시행을 거쳐야 한다. 마찬가지로 역변환을 생각하면 (U,D)-> (D-U,U)

   

6. 이렇게 반복적으로 역변환을 해주면서 string의 앞에 문자를 추가해주면 된다. 원리를 이해하는 것이 어려운 좋은 문제인듯 하다.

---

Source code

#include <iostream>
using namespace std;

int main() {
    int u,d,t;
    scanf("%d/%d",&u,&d);
    string s;
    while (u!=d)
        if (u>d) {
            s.push_back('R');
            t=d,d=u-d,u=t;
        } else if (u<d) {
            s.push_back('L');
            t=u,u=d-u,d=t;
        }
    cout << s;
}