[BOJ] 1057 토너먼트 - JAVA

1. 문제

1057번: 토너먼트

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

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

---

2. 풀이

1.  김지민이 임한수보다 앞 순서이면서 홀수이고 둘 차이가 1일 때 둘은 만난다.

2.  임한수가 김지민보다 앞 순서이면서 홀수이고 둘 차이가 1일 때 둘은 만난다.

3.  김지민이나 임한수 번호가 0 이하라면 둘은 이 대결에서 만나지 못한다.

4.  1,2,3 경우가 모두 아니라면 둘의 번호를 각각 절반씩 줄인다. 번호가 원래 홀수였다면 +1한 뒤 절반을 줄인다. 원래 5번이었다면 그 다음 라운드에서 2번 플레이어가 되는 게 아니라 3번 플레이어가 되기 때문이다.

5.  4번과 동시에 라운드의 개수(count)를 하나씩 더한다.

import java.io.*;
import java.util.*;

public class BOJ_1057_토너먼트 {
   public static void main(String[] args) throws IOException {
      StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
      int N = Integer.parseInt(st.nextToken());
      int kim = Integer.parseInt(st.nextToken());
      int lim = Integer.parseInt(st.nextToken());

      int count = 1;
      while(true){
         if((kim<lim && kim%2==1 && lim-kim==1)||(lim<kim && lim%2==1 && kim-lim==1)){
            System.out.println(count);
            break;
         }
         else if(kim<=0 || lim<=0){
            System.out.println(-1);
            break;
         }
         if(kim%2==1) kim++;
         if(lim%2==1) lim++;
         kim/=2;
         lim/=2;
         count++;
      }
   }
}

---

3. 결과