[백준 1057번 / JAVA ]

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

1057번: 토너먼트

#문제 설명

김지민은 N명이 참가하는 스타 토너먼트에 진출했다.

토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다.

그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다.

만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다.

다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다.

이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다.

이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면,

4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고,

몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다.

1라운드에서 김지민의 번호와 임한수의 번호가 주어질 때,

과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

#입력

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다.

N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

#출력

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

 

#접근 방법

참가하는 총 선수들의 수를 입력하나 구해야 하는 값은 결국 지민이와 한수가 만나는 라운드 번호이다.

지민이와 한수는 만나는 상대방을 무조건 이기고 올라가기 때문에 현재 번호에 따라 다음 라운드 진출 시 매겨질 번호를 계산한다.

짝수 번호일 경우엔 (번호 / 2), 홀수 번호일 경우에는 (번호 / 2 ) + ( 번호 % 2)하면 다음 라운드 진출 시 번호를 구할 수 있다.

번호를 계산해 가면서 지민이를 기준으로 지민이가 짝수일 경우 한수가 1 작고, 홀수 일 경우 한수가 1크다면 현재 라운드의 값을 출력하고 계산을 종료한다.

 

---

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int jimin = sc.nextInt();
		int hansu = sc.nextInt();  
                int Round = 1;
        

		while (true) {
			
			if (jimin % 2 == 0) { // 짝수 지민이
				
				if(jimin == hansu+1) { 
					System.out.println(Round);
					break; 
				}
				
				jimin = jimin / 2; 
			} 
			else {  // 홀수 지민이
				
				if(jimin == hansu-1) {
					System.out.println(Round);
					break;
				}
				jimin = (jimin / 2 + jimin % 2); 
			}
			
			if (hansu % 2 == 0) { // 짝수 한수
				hansu = hansu / 2;
			} 
			else { // 홀수 한수
				hansu = (hansu / 2) + (hansu % 2);
			}
			
		 Round++;
		}

	}

}