[BOJ][Java] 백준 2078번: 무한이진트리

 

문제 설명

다음과 같은 귀납적인 규칙에 의해서 만들어지는 무한한 크기의 이진 트리를 생각하자. 각각의 노드에는 두 정수의 순서쌍이 할당되어 있다.

1. 루트에는 (1, 1)이 할당된다.
2. 어떤 노드가 (a, b)가 할당되었을 때, 그 노드의 왼쪽 자식에는 (a+b, b)가 할당되고, 오른쪽 자식에는 (a, a+b)가 할당된다.

우리는 어떤 노드가 주어졌을 때, 루트에서 그 노드로 이동하는 최단 경로를 찾으려 한다. 하지만 최단 경로가 매우 길 수도 있기 때문에, 왼쪽 자식으로 이동하는 회수와 오른쪽 자식으로 이동하는 회수를 찾으려고 한다.

입력으로 두 정수 A, B가 주어졌을 때, 루트에서 (A, B)가 할당된 노드까지 최단 경로로 이동할 때, 왼쪽 자식으로 이동하는 회수와 오른쪽 자식으로 이동하는 회수를 구해내는 프로그램을 작성하시오.

 

 

 

문제 풀이

이 문제의 경우 처음 접근할 때 루트에서 해당 노드까지 어떻게 내려갈까? 를 고민하게 되는데

반대로 해당노드에서 루트까지 어떻게 가지? 라고 생각을 바꾸게 되면 쉽게 해결할 수 있습니다.

 

자기 자신을 기준으로  (A, B)가 있을 때 A가 B보다 크다면 부모 노드로 부터 왼쪽으로 내려온 것 입니다. 왜냐하면 부모 기준으로 왼쪽 자식은 (a+b, b), 오른쪽 자식은 (a, a+b)이기 때문에 무조건 왼쪽 자식은 왼쪽, 오른쪽 자식은 오른쪽이 클 수 밖에 없습니다.

 

이걸 이용해서 while문을 통해 어떤 노드 (a, b)가 (1, 1)이 될 때까지 조건을 주시면 해결하실 수 있습니다.

 

<입력 예제>(3, 4) -> 오른쪽 자식 노드, 부모: (3, 1)(3, 1) -> 왼쪽 자식 노드, 부모: (2, 1)(2, 1) -> 왼쪽 자식 노드, 부모: (1, 1) 

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    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());

        int left = 0, right = 0;

        while(!(a==1 && b == 1)) {
            if(a < b) {
                b -= a;
                right += 1;
            } else{
                a -= b;
                left += 1;
            }
        }

        System.out.println(left + " " + right);
    }
}

 

<출처>

https://www.acmicpc.net/problem/2078

2078번: 무한이진트리