[백준-자바] 1057번 토너먼트 / 2022.03.31

 

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

1057번: 토너먼트

 

 

import java.util.Scanner;
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(N==1){ // 사람 수가 1명이라면 마지막 round 출력하고 종료
                System.out.println(round);
                return;
            }
            if(jimin-1==hansu || hansu-1==jimin) { // 지민과 한수의 번호차이가 1일 때
                int small = jimin > hansu ? hansu : jimin; // 둘 중 더 작은 번호가
                if (small%2==1){ // 홀수 라면
                    System.out.println(round); // 이번 라운드에서 대결하므로 출력하고 종료
                    return;
                }
            }

            // 지민과 한수가 대결하지 않다면 다음 라운드로
            N /= 2; // 사람수 반으로 줄이고
            if(jimin==1) // 지민의 번호 새로 부여
                jimin = 1; // 1번이라면 계속 1번
            else if(jimin%2==1) // 홀수 번이라면
                jimin = jimin/2+1; // 2로 나누고 + 1
            else // 짝수 번이라면
                jimin = jimin/2; // 2로 나누기기
            if(hansu == 1) // 한수의 번호 새로 부여
                hansu = 1;
            else if(hansu%2==1)
                hansu = hansu/2+1;
            else
                hansu = hansu/2;

            round++; // 다음 라운드로
        }
    }
}

 

풀이 : 

두 사람이 대결을 하기 위한 조건

1. 두 사람의 번호 차이가 1이어야 한다.

2. 두 사람 중 작은 번호가 홀수 이어야 하고 큰 번호가 짝수 이어야 한다.

3. 다음 라운드로 넘어가게 될 경우 새 번호를 부여해야 한다.

4. 짝수라면 나누기 2 홀수라면 나누기 2 + 1

5. 만약 번호가 1번이라면 다음 라운드에도 번호가 1이어야 한다.