[SWEA] 11688, 11689 Calkin-Wilf tree 1, 2

11688 Calkin-Wilf tree 1

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXgZSOn6ApIDFASW

SW Expert Academy

 

11689 Calkin-Wilf tree 2

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXgZVRZKAtIDFASW

SW Expert Academy

 

 

 

Calkin-Wilf tree는 위 그림처럼 a/b를 기준으로 왼쪽 자식 노드는 a/a+b 오른쪽 자식 노드는 a+b/b를 가진다.

특정 입력값을 받았을때 해당하는 숫자가 뭔지 출력하는 문제가 1번 문제이다.
예를 들어 LL을 받으면 1/2 LR을 받으면 3/2같은 결과가 나오면 된다.

T = int(input())
route = ""
for test_case in range(1, T + 1):
    route = input()
    answer = [1,1]
    for i in route :
        if i == "L" :
            answer[1] += answer[0]
        elif i == "R" :
            answer[0] += answer[1]
    print(f"#{test_case} ", end ="")
    print(' '.join(map(str,answer)))

root는 항상 1/1이기 때문에 리스트에 1, 1을 넣고 시작했다.
L이 나오면 b = a + b기 때문에 answer[1] += answer[0]
R이 나오면 a = a + b기 때문에 answer[0] += answer[1] 을하면 쉽게 풀 수 있는 문제이다.

 

2번 문제는 반대로 특정 숫자가 나왔을 때 이 숫자가 어느정도 깊이에 있는지 찾는 문제이다.
이 트리는 항상 큰 쪽이 최근에 더해졌기 때문에 a , b 중에서 어느쪽이 큰지 판단하고 큰 쪽에서 작은 쪽을 빼는 식으로 계산하면 쉽게 풀 수 있었다.

count = 0
while answer[0] == answer[1] == 1:
  if answer[0] > answer[1]:
      answer[0] -= answer[1]
      count += 1
  else
      answer[1] -= answer[0]
      count += 1

이렇게 계산해서 answer[0] 과 answer[1]이 1 되는 순간까지 count를 증가시키면 깊이를 알 수 있게 되지만
시간 초과가 발생하였다. 

그래서 더 단축시키기 위해서 a와 b의 크기를 비교한 뒤 크기가 큰 동안 계속 빼는 것으로
반복문의 횟수를 줄일 수 있게 구현하였습니다.

if b > a:
    a, b = b, a
while b > 1:
    count, a = divmod(a, b)
    answer += count
    a, b = b, a

몫과 나머지를 구해서 값을 변경하는 것으로 더 빠르게 연산을 할 수 있었습니다.
하지만 이렇게 풀어도 시간을 통과하지 못해서 더 찾아보니 출력을 할때 연산 - 출력을 반복하면 안되고
연산*10 출력*10을 해야 통과한다고 해서 코드를 수정하니 통과하였습니다.
아마 OS나오는 spatial locality같은 부분과 관련있는 것 같습니다.

 

 

전체 코드

T = int(input())
answer_list = []
for test_case in range(1, T+1):
    a, b = map(int, input().split())

    if b > a:
        a, b = b, a
    answer = 0
    while b > 1:
        count, a = divmod(a, b)
        answer += count
        a, b = b, a
    else:
        if b == 1:
            answer += a - 1
        else:
            answer = -1
    answer_list.append(answer)

for test_case in range(1, T+1):
    print(f"#{test_case} {answer_list[test_case-1]}")