1057번: 토너먼트 (python, 파이썬)

예제

16 8 9

1 2 3 4 5 6 7 (8) (9) 10 11 12 13 14 15 16
1 2 3 (4) (5) 6 7 8
1 (2) (3) 4
(1) (2) <-- 만남 (4라운드)

1. 초기 번호 k가 주어질때 다음 번호는 int((k+1)/2)다.
2. 왼쪽의 번호가 홀수면서, 두 번호가 연속된 수 일때의 라운드 번호를 출력한다.
   +n이 홀수일때는 고려하지 않아도 됨.

정답 (1)

n, a, b = map(int, input().split())
round = 1

while not (int(a%2) == 1 and a + 1 == b):
  a, b = int((a+1)/2), int((b+1)/2)
  round += 1

print(round)

시간초과가 나왔다..
if문의 복잡한 조건을 계속 확인하느라 오래걸린듯 싶다.

새로운 조건

1. 초기 번호 k가 주어질때 다음 번호는 int((k+1)/2) (k - k //2) 다.
2. 왼쪽의 번호가 홀수면서, 두 번호가 연속된 수 일때의 라운드 번호를 출력한다.
   두 번호가 같아질때의 라운드를 출력한다. (같아질때까지라서, 라운드 0으로 시작)
   +n이 홀수일때는 고려하지 않아도 됨.

정답

n, a, b = map(int, input().split())
round = 0

while a != b:
  a, b = a - a//2, b - b//2
  round += 1

print(round)

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