코드업(codeup) 1936 : (재귀함수) 두 노드간의 거리 C언어

▶문제 : (재귀함수) 두 노드간의 거리 (codeup.kr)

(재귀함수) 두 노드간의 거리

 

▶코드 작성

#include <stdio.h>

int func(int a, int b) {
    if (a == b) return 0;//위로 올라가 만나는 지점
    if (a > b) a /= 2;//큰 수를 2로 나누기
    else b /= 2;
    return func(a, b) + 1;//올라가는 횟수
}

int main() {
    int a, b;

    scanf("%d %d", &a, &b);

    printf("%d", func(a, b));

    return 0;
}

 

▶해석

노드의 트리 구조를 보면 자식 노드를 2로 나누면 부모 노드가 된다는 것을 알 수 있다.

따라서 구하고자 하는 두 노드를 큰 수 먼저 2로 나누다 보면 어느새 값이 같아지는데 그 부분이 바로 위로 올라가서 만나는 부분이다.