728x90
반응형
문제 : https://codeup.kr/problem.php?id=1936
문제 설명
21억21억이하로 구성된 완전 이진 트리가 있다.
노드의 번호는 루트 노드에서 부터 상->하, 좌->우방향으로 1,2,3,4,...1,2,3,4,... 로 차례대로 부여 된다.
이 때 두 노드 a,ba,b의 거리를 구하고자 한다.
예를 들어, 33번 노드와 44번 노드의 거리는 33이고, 44번 노드와 55번 노드의 거리는 22이다.
금지 키워드 : for while goto
입력
두 노드 a,ba,b가 입력된다.(1<=a,b<=2,100,000,0001<=a,b<=2,100,000,000)
출력
두 노드 a,ba,b의 거리를 출력한다.
입력 예시
3 4
출력 예시
3
코드 :
# include <stdio.h>
int LCA(int a,int b)
{
if(a == b)
return 0;
if(a>b)
return LCA(a/2,b)+1;
if(a<b)
return LCA(a,b/2)+1;
}
int main()
{
int a,b;
scanf("%d %d",&a,&b);
printf("%d",LCA(a,b));
return 0;
}
728x90
반응형
최근댓글