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

---

문제설명

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

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

사고과정

• 특정한 자료구조나 알고리즘을 사용하는 문제보다는 규칙을 파악하는 문제인 듯 싶었다. 서로 인접한 번호끼리 묶은 후, 새로운 번호를 부여받는 것인데, 입력 예시로 규칙을 찾아보니, 각 원소가 2로 나누어떨어질 때, 떨어지지 않을 때에 따라 처리해주는 규칙을 찾은 후(소스코드에서 divide 함수) 이 규칙을 계속 적용하면서 a == b가 될 때의 Round - 1 을 해주면 된다. 처음에는 a 와 b가 인접할 경우 즉, a + 1 == b or b + 1 == a 일 때, return 하도록 작성해주었는데, 몇개의 테스트 케이스에서 오류가 떴다. 반례를 질문하기를 통해서 얻었는데, 만약 N=8 , a = 4, b =5 라고 한다면, 정상적으로 동작하면 답이 3이 나와야 하지만  a + 1 == b or b + 1 == a  이 조건을 넣어주게 되면 답이 1이 나오게 된다. 따라서 이를 고려하여 a == b일 경우에만 바꾸도록 설정해주니 통과가 되었다!

풀이

def divide(x):
    if x % 2 != 0:
        x = x // 2 + 1
    else:
        x //= 2
    return x


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

    while True:
        a = divide(a)
        b = divide(b)
        if a == b:
            return answer
        answer += 1