[백준] 토너먼트 (1057번)

힌트

문제 이해

• 이 문제는 이진 트리 구조에서 두 개의 노드가 주어질 때, 이 두 노드가 부모 노드를 통해 만나는 경로를 찾는 문제입니다.
• 주어진 노드가 서로 만나기 위해서는 서로의 부모 노드로 이동해야 하며, 이 과정에서 몇 번의 이동이 필요한지를 계산합니다.

핵심 아이디어

1. 부모 노드 계산:
   • 이진 트리에서 부모 노드는 다음과 같이 계산할 수 있습니다:
     • 부모 노드 = (자식 노드 - 1) / 2 + 1
   • 이 공식을 사용하여 두 위치(pos1, pos2)의 부모 노드를 반복적으로 계산합니다.
2. 만나는 조건:
   • 두 위치가 동일할 때까지 부모 노드로 이동합니다.
   • 이동하는 횟수를 카운트하여 최종 결과를 출력합니다.

알고리즘 흐름

1. 사용자로부터 노드 수와 두 위치를 입력받습니다.
2. 두 위치가 서로 다를 때까지 부모 노드로 이동합니다.
3. 이동한 라운드 수를 카운트하여 출력합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성

        int n, pos1, pos2, round; // n: 노드 수, pos1: 첫 번째 위치, pos2: 두 번째 위치, round: 라운드 수
        
        n = in.nextInt(); // 전체 노드 수 입력
        pos1 = in.nextInt(); // 첫 번째 위치 입력
        pos2 = in.nextInt(); // 두 번째 위치 입력
        round = 0; // 초기 라운드 수 설정
        
        // 두 위치가 같아질 때까지 부모 노드로 이동
        while (pos1 != pos2) {
            pos1 = (pos1-1) / 2 + 1; // pos1의 부모 노드로 이동
            pos2 = (pos2-1) / 2 + 1; // pos2의 부모 노드로 이동
            round++; // 라운드 수 증가
        }
        
        System.out.println(round); // 두 위치가 만나는 라운드 수 출력
    }
}