[구현/수학] 백준 27724 팝핀 소다 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

27724번: 팝핀 소다

 

 

 

2. 문제 풀이

 2의 거듭제곱수로 진행되는 토너먼트에서 시은이가 최대로 이길 수 있는 경기 수를 구하는 문제입니다. 입력으로 각 선수의 기량이 주어지며, 기량이 높은 선수가 승리하게 됩니다. 다만, 이변이 일어났을 경우에는 기량이 더 적은 선수가 승리합니다.

 시은이가 최대한 많은 승리를 하기 위해서는, 일단 기량별로 정렬해서 강자는 강자끼리 약자는 약자끼리 붙어야 합니다. 그리고 시은이가 강자와 붙었을 때, 이변 횟수를 사용해서 최대한 승리합니다.

 

 

3. 코드

import math

n, m, k = map(int, input().split())

total_game = int(math.log(n, 2))
win = int(math.log(k, 2))
print(min(win + m, total_game))

 토너먼트이므로, 시은이가 1등을 하기까지 겨뤄야하는 경기 수는 log2_n입니다.

 선수들의 기량은 1부터 N까지 순위로 주어지므로, 시은이의 기량이 K일 때 승리할 수 있는 총 횟수는 log2_k입니다.

 여기서 이변이 일어났을 경우만 고려하면 최대 승리 수가 됩니다.