[SWEA] 11688. Calkin-Wilf tree 1 (Python/D3)

---

[문제 링크] 👇

SW Expert Academy

---

Calkin-Wilf Tree

Calkin-Wilf Tree는 모든 양의 유리수를 중복 없이 포함하는 이진 트리이다. 트리의 각 노드는 부모 노드의 분수 ab\frac{a}{b}ba​를 기준으로 왼쪽 자식은 aa+b\frac{a}{a+b}a+ba​, 오른쪽 자식은 a+bb\frac{a+b}{b}ba+b​ 형태로 생성된다. 이를 통해 유리수를 순서대로 탐색할 수 있다.

 

풀이

입력이 LRL 이라고 하자. 그럼 다음 그림과 같다.

 

따라서 문자가 L이면 Right 값에 L 값을 더해 누적하고, R이면 Left 값에 R 값을 더해 누적시킨다.

마지막으로 Left값과 Right값을 출력한다.

 

 

Solution

test_case = int(input())
for tc in range(1, test_case + 1):
    node = input().strip()
    l = 1
    r = 1
    for i in node:
        if i == 'L':
            r += l
        else:
            l += r
    print("#%d %d %d" %(tc, l, r))

 

---