[Python] 11688. Calkin-Wilf tree 1

SW Expert Academy

문제풀이

- 현재 가리키고 있는 노드가 1/1이고, 현재 노드가 a/b를 가리키고 있다면 왼쪽 자식은 a/a+b, 오른쪽 자식은 a+b/b를 나타낸다는 것에 집중한다.

 

import sys
sys.stdin = open('sample_input.txt', 'r')

T = int(input())
for t in range(1, T+1):
    sList = input()
    a, b = 1, 1

    for s in sList:
        if s == 'L':
            a = a
            b = a + b
        elif s == 'R':
            a = a + b
            b = b

    print('#{} {} {}'.format(t, a, b))