1. 문제
https://www.acmicpc.net/problem/2078
2078번: 무한이진트리
첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다.
www.acmicpc.net
2. 풀이
import sys
input = sys.stdin.readline
l, r = map(int, input().split())
lCnt, rCnt = 0, 0
def search(l, r):
global lCnt, rCnt
# print("l :", l, "r :", r)
# print()
if l == 1 and r == 1:
return
if l == 1:
rCnt += r - 1
return
if r == 1:
lCnt += l - 1
return
if l > r:
lCnt += l // r
search(l%r, r)
if l < r:
rCnt += r // l
search(l, r%l)
search(l, r)
print(lCnt, rCnt)