[알고리즘] 백준 1057번 토너먼트 python

Created

2022/07/09

Tags

Algorithm

Python

Implementation

Brute Force

2022-07-09 @이영훈

1057번: 토너먼트

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다.

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

두 플레이어가 경기하는 경우는 자신의 번호를 2로 나눈 몫과 나머지를 더했을 때 같은 경우이다

예를들어 1과 2인 경우 2로 나눈 몫과 나머지를 더했을 때 같기 때문에 다음 경기에서 만난다

•

(1 // 2 + 1 % 2) = (0 + 1) = 1

•

(2 // 2 + 2 % 2) = (1 + 0) = 1

그리고 전체 플레이어 수(n)는 한 차례의 토너먼트를 거치면 2로 나눈 몫과 나머지를 더한만큼으로 줄어든다

•

n이 4인 경우, (4 // 2 + 4 % 2) = (2 + 0) = 2로 줄어들고

•

n이 5인 경우, (5 // 2 + 5 % 2) = (2 + 1) = 3으로 줄어든다.

def next_number(num):
    return (num // 2) + (num % 2)


n, player1, player2 = map(int, input().split())

answer = 0
while True:
    answer += 1

    player1 = next_number(player1)
    player2 = next_number(player2)
    if player1 == player2:
        break

print(answer)
Python
복사