코드업(CodeUp) - C 1935번 - (재귀함수) LCA

문제 : https://codeup.kr/problem.php?id=1935

(재귀함수) LCA

 

문제 설명

21억21억이하로 구성된 완전 이진 트리가 있다.

노드의 번호는 루트 노드에서 부터 상->하, 좌->우방향으로 1,2,3,4,...1,2,3,4,... 로 차례대로 부여 된다.

이 때 두 노드 a,ba,b의 가장 가까운 공통 조상(LCA:LowestCommonAncestorLCA:LowestCommonAncestor) 노드를 찾아서 출력하시오.

예를 들어, 33번 노드와 44번 노드의 LCALCA는 11번 노드이다. 그리고 66번 노드와 77번 노드의 LCALCA는 33번 노드이다.

금지 키워드 : for while goto

 

 

입력

두 노드 a,ba,b가 입력된다.(1<=a,b<=2,100,000,0001<=a,b<=2,100,000,000)

출력

두 노드 a,ba,b의 가장 가까운 공통 조상 노드(LCA:LowestCommonAncestorLCA:LowestCommonAncestor)를 출력한다.

 

입력 예시

3 4

출력 예시

1

 

 

코드 : 

# include <stdio.h>

int LCA(int a,int b)
{
	if(a == b)
		return a;
	if(a>b)
		return LCA(a/2,b);
	if(a<b)
		return LCA(a,b/2);
}

int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	printf("%d",LCA(a,b));
	
	return 0;
}