[백준 1057번 문제, JAVA] 토너먼트

문제

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split("\\s+");
        int[] user = new int[2];
        user[0] = Integer.parseInt(input[1]);
        user[1] = Integer.parseInt(input[2]);

        int count = 0;
        while (user[0] != user[1]) {
            if (user[0] > 1) {
                user[0] = (int) Math.ceil((float) user[0] / 2);
            }

            if (user[1] > 1) {
                user[1] = (int) Math.ceil((float) user[1] / 2);
            }

            count++;
        }
        System.out.println(count);
    }
}

---

해결

인원수가 11명이고 5번째, 9번째가 만날 때 까지 대진표를 그려봤다

그랬더니 현재 번호를 2로 나누었을 때 나머지를 올림한 것으로 계속 나와서 계속 그려봤는데

몫이 1일 때 까지 반복한 횟수가 경기 횟수가 되는 것을 볼 수 있었다

---

참고

링크