[프로그래머스 LEVEL2 : 예상 대진표][python]

https://school.programmers.co.kr/learn/courses/30/lessons/12985#

프로그래머스

import math

def solution(n,a,b):
    answer = 0
    
    while (n >= 2):

        if (a <= n //2 and b > n //2) or (a > n//2 and b <= n //2):
            answer = math.log2(n)
            break
            
        elif a > n//2 and b > n//2:
            a -= n//2
            b -= n//2
            
        n = n //2

    return answer

- 아이디어

1. 예를 들어, n이 8인 경우, a와 b가 각각 1, 5와 같이 n/2를 기준으로 양쪽으로 나뉜 경우, 두 경쟁자가 만나는 지점은 항상 맨 마지막 라운드 즉, log2(n)번째 라운드이다. 

 

2. 만약 n이 8인 경우에 a,b가 각각 1,4와 같이 n/2를 기준으로 왼쪽에만 있는 경우, 해당 문제는 n / 2일 때와 같은 문제로 나눌 수 있고, 1번 조건을 다시 적용할 수 있다. 

 

3. 그러나 2번 조건을 만족하지 않는 경우는 n이 8일때 a,b가 각각 6,8 처럼 n/2 기준으로 오른쪽에 있는 경우에는 n/2가 a,b보다 작아지므로 1번 조건을 만족시키는 경우가 절대 나오지 않게되는데, 이때 토너먼트 대진은 반드시 좌우 대칭형태이므로 예시를 기준으로 a,b에서 n/2만큼 빼주게 되면 a,b가 2, 4로 바뀌고 이는 2번의 조건을 적용할 수 있어 반드시 정답을 찾을 수 있다. 

 

 

-- 깨달음

: 여러가지 정답이 있으나, 이 방법이 나에게는 가장 직관적인 듯 함