📙[Algo] 24.01.08 알고리즘

1057번: 토너먼트

문제 요약

• N명이 참가하는 스타 토너먼트
• 인접한 번호끼리 스타 ⇒ 이기면 다음 라운드 진출
• 만약 홀수명이라면 마지막 번호는 자동 진출
• 다음 라운드 번호 매기는 순서도 처음 번호의 순서 유지
• 김지민, 임한수 번호가 주어질 때 둘이 몇 라운드에서 대결하는 지 출력
  • 김지민과 임한수는 계속 이긴다고 가정

시간 제한 
1초

입력
참가자수 N, 1라운드에서 김지민 번호와 임한수 번호
   - (2≤N≤100,000 , 1≤김지민 ≠ 임한수 ≤N)

출력
김지민과 임한수가 대결하는 번호 출력
   - 만약 대결하지 않으면 -1 출력

 

접근법

(19) 20 (10) 31

(9) 10 (5) 16

(4) 5 (2) 8

(2) 3 4

---

(7) 8 9

(3) 4 5

(1) 2 3

(0) 1 2

---

(0) 1 2

• 지민 점수 % 2 == 0
  • 앞에 -1(단 앞의 갚이 0보다 클 경우)
• 지민 점수 %2 != 0
  • 뒤에 -1(단 뒤의 값이 0보다 클 경우)
• 한수 점수 %2 == 0
  • 앞에 -1(단 앞의 값이 0보다 클 경우)
• 한수 점수 %2 != 0
  • pass
• 위에 처리 후 각각 지민 점수 앞에 있는 인원, 지민과 한수 사이에 있는 인원이 0보다 클경우 2로 나눠준다.
• 지민이 홀수, 한수가 짝수이면서 둘의 차이가 1일 때까지 진행
• 남은 인원 수가 2명 될 때까지 진행
• 헏… 지민이가 한수보다 점수가 더 높을 수 있음 ^^

 

코드

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 J = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        if(J>H){
            int tmp = J;
            J = H;
            H = tmp;
        }

        int round = 0, a = J - 1, b = H - J - 1;
        while(N-- > 1){

            if (H - J == 1 && J % 2 != 0 && H % 2 == 0) {
                round++;
                break;
            }

            if (J % 2 == 0) {
                if (0 < a) {
                    a--;
                }
            } else {
                if (0 < b) {
                    b--;
                }
            }

            if (H % 2 == 0) {
                if (0 < b) {
                    b--;
                }
            }

            if (a > 0) {
                a /= 2;
            }

            if (b > 0) {
                b /= 2;
            }

            J = a + 1;
            H = J + b + 1;

            round++;

        }

        if(round ==0 ) System.out.println(-1);
        else System.out.println(round);
        
    }
}