[Programmers] 예상 대진표

예상 대진표

예상 대진표 를 클릭하면 바로 이동한다.

A 와 B 의 번호를 주고 이 둘이 몇 라운드에 만나는지를 구하면 되는 문제이다.

이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다.

N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다.

그리고, 1번↔2번, 3번↔4번, … , N-1번↔N번의 참가자끼리 게임을 진행합니다.

각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다.

이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다.

만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고

3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다.

게임은 최종 한 명이 남을 때까지 진행됩니다.

A 가 10 번 이라면 10, 5, 3, 2, 1 순으로 진행 된다고 생각하면 된다.

---

서로 만나는 경우가 되려면 A, B 의 차이가 1 이면서 큰 값이 짝수이면 된다.

처음에 이 경우를 생각하지 못해 일부 테스트케이스는 틀렸다.

예를들어 8, 9 인 경우 4 라운드때 만나야 하는데 1 라운드에 만난다고 반환을 하는가 하면

7, 8 인경우 1 라운드에 바로 만나는데 3 라운드에 만난다고 반환을 했다.

역시 여러 경우를 손으로 그리면서 해봐야 바로 느낌이 온다.

from math import ceil


def solution(n, a, b):
	round = 1

	while True:
		if max(a, b) - min(a, b) == 1 and max(a, b) % 2 == 0:
			break

		a = ceil(a / 2)
		b = ceil(b / 2)
		round += 1

	return round