프로그래머스 - 예상 대진표 (2017 팁스타운) [Python]

 

 문제

 

programmers.co.kr/learn/courses/30/lessons/12985

코딩테스트 연습 - 예상 대진표

 

 

 

 

 

 

 문제 상황

 

- 1번부터 n번까지 사람이 게임을 진행한다고 할 때 a, b는 모든 게임에서 이긴다는 조건으로 게임을 진행한다. a와 b가 만날 때까지 진행된 게임의 수를 계산한다.

 

 

 

 

 

 

 해결 전략

 

- 주어진 수를 2로 나누며 같아질 때까지 반복하여 그 횟수를 출력한다.

 

 

 

 

 

 코드

 

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

 

 

 

 

 

 

 

 

 해설

 

- 게임의 수는 사실 상관이 없는 문제다. n은 2의 지수승이므로 부전승이 발생하지 않고, 0 1이 대결하면 0이 이기고, 2 3이 대결하면 항상 2가 남는다고 전제하면 0 1의 승자는 0//2 혹은 1//2가 된다. 그래서 예시의 4가 7과 만나려면 인덱스에서는 3, 6이 만나야 하고, 두 수를 2로 나눈 몫이 같아질 때까지 연산을 반복한다.

 

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 알고리즘 자체가 어려운 문제가 아니라 수학적으로 개념을 이해하는 문제이다.