백준 1057 : 토너먼트 ( Python )

문제 링크

📌 사용 알고리즘 : bitmasking , bruteforcing

두명의 선수가 토너먼트를 할 시 몇번째 경기에서 만날지 구하는 문제입니다.

Naive 하게 탐색한다면 1~2 구간 , 3~4 구간 , ••• , N-1 ~ N 구간 까지 살핀후에 두 사람이 같은 경기를 치르는지 확인합니다.

그렇지 않다면 1~4 구간 , 5~8 구간 , ••• , N-3 ~ N 구간 까지 살핍니다.
이렇게 두 사람이 같은 구간에 속할때 까지 구간의 크기를 2배씩 늘리면서 확인해줍니다.

시간복잡도는 O(NlogN) 입니다.

조금 더 간단히 생각해봅시다.
토너먼트를 한 경기를 할 때마다 인원의 수는 2배씩 줄어듭니다.

def tournament(a,b):
    bit = 0
    while a!=b:
        a -= a//2
        b -= b//2
        bit+=1
    return bit

인원수가 2배씩 줄어든다는 것은 나의 번호가 2배씩 감소한다는 것이므로
위 함수를 사용하면 O(logN) 의 시간복잡도로 해결 가능합니다.

📌 코드

import sys,math
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

def tournament():
    bit = 1
    while (1 << bit) <= N*2:

        start = 1
        end = 1 << bit

        while end <= N*2:
            if start <= jimin <= end and start <= hansu <= end:
                return bit
            start += 1<<bit
            end += 1<<bit
        bit += 1
    return 0

N,jimin,hansu = MI()

ans = tournament()

if ans:print(ans)
else: print(-1)

import sys,math
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

def tournament(a,b):
    bit = 0
    while a!=b:
        a -= a//2
        b -= b//2
        bit+=1
    return bit

N,jimin,hansu = MI()
print(tournament(jimin,hansu))