[백준]무한이진트리(2078)

문제 링크 : [백준]무한이진트리(2078)

2078번: 무한이진트리

 

문제 설명

루트가 (1, 1)의 값을 갖는 노드로 이루어지며, 왼쪽 자식은 (2, 1), 오른쪽 자식은 (1, 2)로 이루어집니다.

반복적으로 왼쪽 자식은 (부모의 왼쪽 값 + 부모의 오른쪽 값, 부모의 오른쪽 값), 오른쪽 자식은 (부모의 왼쪽 값, 부모의 왼쪽 값 + 부모의 오른쪽 값) 으로 구성됩니다.

이 때, 왼쪽 값과 오른쪽 값이 주어졌을 때, 해당 값이 나오는 노드에 도착하기 위하여 루트 노드에서 왼쪽, 오른쪽으로 몇번을 이동해야 하는지 구하세요.

입력

A B(왼쪽 값과 오른쪽 값, 1 <= A, B <= 2,000,000,000)

3 4

 

출력

2 1

 

카테고리

#수학

 

시간 복잡도 상한

O(N)

 

해결 방법

1. 주어진 값 중 왼쪽 값이 더 크다면 부모 노드에서 왼쪽으로 이동한 경우입니다.
2. 마찬가지로 오른쪽 값이 더 크다면 부모 노드에서 오른쪽으로 이동한 경우입니다.
3. 그리고 부모 노드의 값은 값이 작은 쪽은 유지하고, 큰 쪽은 큰 값에서 작은 값을 뺀 값이 됩니다.
   1. 예시) (5, 2) 였다면 부모 노드에서 왼쪽으로 이동하였고, 부모는 (3, 2)입니다.
4. 이것을 반복적으로 하면 됩니다.
5. 하지만 한쪽으로 치우친 경우, (2,000,000,000, 1) 같은 경우 타임아웃이 납니다.
6. 만약 한쪽으로 K번 이동하게 된다면, 이동한 방향의 반대쪽의 값을 K번 더하게 됩니다.
   1. (3, 2)였다면, 오른쪽으로 3번 이동하게 되면, (3, 5) -> (3, 8) -> (3, 11) = (3, 2 + 3 * 3) 이 됩니다.
7. 그리고 그 시작점은 반드시 이동한 방향의 반대쪽 값이 더 크게 됩니다.
   1. 그렇지 않다면 이전에도 같은 방향으로 이동한 경우이기 때문입니다.
8. 따라서 아래와 같은 식을 구할 수 있습니다.
   1. 왼쪽 값이 크다면, 왼쪽으로 이동한 칸수 = 왼쪽 값 / 오른쪽 값
   2. 오른쪽 값이 크다면, 오른쪽으로 이동한 칸수 = 오른쪽 값 / 왼쪽 값
9. 한 방향으로 이동한 횟수를 구한 다음, 3.을 이용하여 부모 노드의 값을 구하고, 다시 같은 방향으로 이동한 횟수를 구하는 연산을 반복하면 됩니다.
10. 타임아웃은 한방향으로 이동한 경우 값이 선형으로 증가하여 발생하나, 위 수식으로 빠르게 계산 할 수 있고, 그렇지 않은 경우, 값이 빠르게 증가하여 타임아웃을 피할 수 있습니다.

시간복잡도

O(빠름)

코드

#include<cstdio>
int a,b,x,y;
int main(){
    scanf("%d%d",&a,&b);
    while(1){
        if(a==1){y+=b-1;break;
        }else if(b==1){x+=a-1;break;}
        if(a>b)x+=a/b,a%=b;
        else y+=b/a,b%=a;
    }
    printf("%d %d",x,y);
}