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

출처 https://school.programmers.co.kr/learn/courses/30/lessons/12985/solution_groups?language=python3&type=my 

프로그래머스

문제

• 2의 거듭제곱 수 만큼의 참가 인원이 주어지고 참가자는 각자의 번호를 가진다.
• 하나의 라운드를 거칠 때마다 참가자의 번호가 달라진다.
• 1,2번 참가자가 경기를 하여 이긴 사람이 1번이 되고, 3,4번 중 이긴 사람이 2번이 되는 것이다. 
• 임의의 두 참가자의 시작 번호가 주어질 때 두 사람이 만나게 되는 라운드를 구하면 된다.

---

나의 생각 

• 대진표의 모양 때문인지 비교적 최근에 배운 이진트리가 먼저 생각이 났다.  루트 노드의 간격에 따라서 정답이 정해지기 때문에 무언가 그럴싸 했다. 하지만 부족했던 건 나의 능력. 상황에 맞게 응용해서 구현하지 못했다. 
• 다음으로 한 것은 인원을 8명으로 두고 상황을 생각해보았다. 현재 번호와 다음 라운드의 숫자를 써놓고 보니 패턴이 보였다.

     1                2                3            ···    

1      2       3       4       5       6      ···

 

• 위와 같은 형태를 보았을 때 이전 라운드에서의 숫자를 2로 나누는 것과 관련이 있는게 분명했다. 

1.  숫자를 2로 나눈 몫 + 2로 나눈 나머지 

2. 1을 더해 2로 나눈 몫

• 위 두가지가 눈에 들어왔고 바로 실행에 옮겨보았다.

def solution(n,a,b):
    cnt = 0
    while a!=b:
        #2로 나눈 나머지 + 몫 -> 다음 라운드의 숫자가 된다.
        a = (a//2) + (a%2) 
        b = (b//2) + (b%2)
        cnt+=1
    return cnt

def solution(n,a,b):
    cnt = 0
    while a!=b:
        a = (a+1//2) 
        b = (b+1//2) 
        cnt+=1
    return cnt

두 가지 방법 모두 잘 실행되었다!

수학적 식을 사용하는 경우가 꽤 많은 것 같다고 느꼈다.  항상 다른 시각에서도 바라볼 수 있는 능력이 중요하겠다.