[python/파이썬] 백준 1057 토너먼트

[문제 출처]

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

1057번: 토너먼트

 

[소스 코드1 - 틀렸습니다]

 

n명의 참가자가 있을 때 두 사람이 몇 라운드에서 만나는지 알기 위해서는

2^i 만큼 묶어보면 알 수 있다.

예를 들어 n = 16 kim = 8 im = 9라고 할 때

 

(1) 2^1

1 2 / 3 4 / 5 6 / 7 8 / 9 10 / 11 12 / 13 14 / 15 16

 

(2) 2^2

1 2 3 4 / 5 6 7 8 / 9 10 11 12 / 13 14 15 16

 

(3) 2^3

1 2 3 4 5 6 7 8 / 9 10 11 12 13 14 15 16

 

(4) 2^4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

>> 같은 묶음 안에 8과 9가 위치하므로 4라운드에서 8번과 9번은 만난다.

 

이 과정을 코드로 표현하기 위해서 ceil함수를 사용했다.

아래 코드를 보면 2의 제곱, 세제곱 이런 식으로 나눠주는 수를 2씩 곱해주었고, 

그렇게 나눠 준 수에 ceil을 했을 때 나온 값이 같다면 같은 묶음 안에 있는 것이다.

 

ceil(8/2) = ceil(4) = 4

ceil(9/2) = ceil(4.5) = 5

 

ceil(8/4) = ceil(2) = 2

ceil(9/4) = ceil(2.25) = 3

...

ceil(8/16) = 1

ceil(9/16) = 1

 

#1057
import math
n, kim,im = map(int, input().split())

for i in range(1,int(n**(1/2))+1):
  if math.ceil(kim/(2**i)) == math.ceil(im/(2**i)):
    round = i
    break    
print(round)

 

하지만 제출을 했을 때 틀렸다고 떴기에 다른 코드로 작성해 주었다.

틀린 부분이 보인다면 댓글 달아주시면 감사하겠습니다.

 

[소스 코드2 - 맞았습니다!!]

 

위의 코드와 기본 아이디어는 동일하나 2로 계속 나눠주어 나눈 횟수를 계산하여 round 수를 계산하였다.

#1057
import math

n, kim,im = map(int, input().split())

round = 0
while True:
  if math.ceil(kim) == math.ceil(im):
    break
  kim = math.ceil(kim/2)
  im = math.ceil(im/2)
  round += 1

print(round)