백준 No.1057 토너먼트- JAVA

 

문제

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

 

 

풀이

애초에 N은 필요없는 숫자였다... 다 풀고 암

jm 과 hs 변수를 만들어 각 값을 할당하고 이 값들은 서로 다른 값인데 짝수일 수도 홀수일 수도 있어서 jm%2로 나머지를 두 수에 더해야하고 토너먼트를 통해 반으로 쪼개지기 때문에 jm/2 + jm%2를 했다. 이렇게 다가가다보면 두 수는 만나게 되고 만나면 break를 통해 반복문을 빠져나오면 된다. 반복문이 반복한 횟수 출력하면 되는데 문제에서 안 만나면 -1을 출력하라 했는데 테스트 케이스에 -1을 출력하는 예제가 없나보다 -1 예제 있었으면 해당 코드는 아무 값도 출력 못하거나 시간초과 남

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {


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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int jm = Integer.parseInt(st.nextToken());
        int hs = Integer.parseInt(st.nextToken());

        int count = 1;

        while (true){
            jm = jm/2+jm%2;
            hs = hs/2+hs%2;

            if(hs == jm) break;
            count++;
        }
        if(hs == jm) System.out.println(count);
    }
}