[Python] 프로그래머스 12985. 예상 대진표 (Lv.2)

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

프로그래머스

 

약간의 수학적 사고력이 필요한 문제입니다.

 

우선 두 팀이 가장 늦게 만나는 경우는 결승전에서 만나는 경우입니다. 그럼 총 n개의 팀이 있을 때 결승전까지 몇 단계의 경기가 필요할까요?

 

n = 2이면 1, n = 3이면 2,  n = 4이면 2, n = 5이면 3... 즉 팀이 n개 이면 정답이 될 수 있는 가장 큰 값은 log(2) N을 올림한 값이 됩니다. 이 값을 매치의 갯수, M이라고 합시다. 우리는 M이 1부터 log(2) N 사이라는 걸 알았습니다. 그렇다면 정확한 M의 값은 어떻게 구할까요?

 

 

우선 N = 8인 케이스에서 M이 가장 큰 경우를 생각해보겠습니다.

 

 

M이 가장 큰 경우는 위와 같은 모습일겁니다. 결승전에서 만나는 팀은 결승전을 기준으로 왼쪽 팀, 혹은 오른쪽 팀 입니다. 

팀이 N개라면 팀 순서가 2^M/2 이하인 팀이 왼쪽에서 결승전에 오르는 팀이고 팀순서가 2^(M-1) 보다 큰 팀이 오른쪽에서 결승전에 오르는 팀 입니다. 

 

팀이 8개라면 log(2) 8 = 3이고 2^(3-1) = 4이므로 4 이하인 1~4번 팀은 결승전 기준으로 왼쪽팀이 되고 5~8번 팀은 결승전 기준으로 오른쪽 팀이 됩니다. 이때 두 팀은 모든 팀이 속한 크기가 8인 블록에서는 같은 블록에 속하지만 크기가 4인 블록에선 서로 다른 블록에 있죠.

 

 

 

만약 두 팀이 4강에서 만나는 경우는 어떨까요?

두 팀이 결승전보다 먼저 만난다면 결승전을 기준으로 같은 방향에 있는 팀이라는 뜻입니다. 즉 위 그림처럼 1번 팀, 3번 팀 모두 4이하로 왼쪽에 속합니다. 또 이들은 1~4번 팀을 기준으로 보면 log(2) 4 = 2이고 2^(2-1) = 2 이하인 1번 팀과 2 초과인 3번 팀으로 서로 다른 방향에 있습니다. 이때 두 팀은 크기가 4인 블록에는 함께 속합니다. 크기가 2인 블록에선 서로 다른 블록에 있습니다.

 

 

 

슬슬 규칙을 찾으셨을거라고 생각합니다. 3번과 4번 팀은 8강에서 만나고 이 두 팀은 2를 기준으로 2보다 큰 팀입니다. 이때 두 팀은 크기가 2인 블록에 함께 속합니다. 이보다 더 작은 크기의 블록은 없습니다.

 

즉 우리는 위에서 부터 블록 사이즈를 줄여가며 어느 단계에서 두 팀이 다른 블록에 있는지를 찾으면 거꾸로 어떤 단계에서 두 팀이 만나는지를 알 수 있습니다.

 

import math

def solution(n,a,b):
    answer = math.log2(n)
    a, b = a - 1, b - 1
    
    while n > 1:
        n //= 2
        if a // n == b // n:
            answer -= 1
        else:
            break

    return answer

 

코드는 이렇습니다.

블록의 사이즈가 되는 n 값을 줄여가며 a 와 b를 n으로 나눈 몫이 달라진다면 두 팀은 다른 블록에 속하는 것이고 그 단계에서 만나게 됩니다.