# [Silver II] 무한이진트리 [문제 링크](https://www.acmicpc.net/problem/2078) ## 문제 설명 <p>다음과 같은 귀납적인 규칙에 의해서 만들어지는 무한한 크기의 이진 트리를 생각하자. 각각의 노드에는 두 정수의 순서쌍이 할당되어 있다.</p> <ol> <li>루트에는 (1, 1)이 할당된다.</li> <li>어떤 노드가 (a, b)가 할당되었을 때, 그 노드의 왼쪽 자식에는 (a+b, b)가 할당되고, 오른쪽 자식에는 (a, a+b)가 할당된다.</li> </ol> <p>우리는 어떤 노드가 주어졌을 때, 루트에서 그 노드로 이동하는 최단 경로를 찾으려 한다. 하지만 최단 경로가 매우 길 수도 있기 때문에, 왼쪽 자식으로 이동하는 회수와 오른쪽 자식으로 이동하는 회수를 찾으려고 한다.</p> <p>입력으로 두 정수 A, B가 주어졌을 때, 루트에서 (A, B)가 할당된 노드까지 최단 경로로 이동할 때, 왼쪽 자식으로 이동하는 회수와 오른쪽 자식으로 이동하는 회수를 구해내는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다.</p> ## 출력 <p>첫째 줄에 두 정수 L, R을 출력한다. 각각은 왼쪽으로 이동한 회수, 오른쪽으로 이동한 회수를 나타낸다.</p> ## 풀이 거꾸로 (A, B)에서 (1, 1)로 이동하면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int a, b; cin >> a >> b; int cnt1=0, cnt2=0; while(a!=1 && b!=1) { if(a>b) { cnt1 += a/b; a%=b; } else { cnt2 += b/a; b%=a; } } cout << cnt1+a-1 << ' ' << cnt2+b-1; } ```