[CodeUp_Java] Q1935 : LCA (3n+1)

안녕하세요! Plitche(플리체)입니다.
이번 포스팅의 주제는 Q1935 : [재귀함수] LCA (3n+1) (자바, JAVA)입니다.

Intro

• CodeUp(코드업) 문제 확인하기
• Github(깃헙) 풀이 확인하기

Question

문제 설명

입력

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

출력

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

예시

• 입력 : 3 4
• 출력 : 1

Solution (풀이)

• 풀이 : 메모리 11148, 시간 : 69

public class Answer1 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        System.out.println(loop(a, b));
    }

    public static int loop(int a, int b) {
        if (a==b) { // 동일한 숫자가 되면 a를 리턴하고 멈춘다.
            return a;
        } else if(a>b) { // a가 b보다 크면 a를 /2 해서 파라미터로 넘긴다.
            return loop(a/2, b);
        } else {
            return loop(a,b/2); // 반대의 경우  b를 2로 나눈다.
        }
    }

}

Ranking(순위)