[Programmers] 예상대진표

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12985

해설

N명이 게임에 참가하고 1<->2, 3<->4, 5<->6, ... N-1<->N 규칙으로 대결을 한다. 그리고 이긴 승자는 다음라운드에 진출하고 다시 번호를 부여 받는다. 이 규칙을 표현하면 다음과 같다.

'''

1 2   3 4   5 6   7 8

  1     2      3     4

     1             2

'''

여기서 다음 라운드 숫자의 번호를 구하는 규칙은 현재 번호에서 2로 나눈 나머지와 몫을 더하면 다음 라운드의 번호가 된다. 그리고 다음 라운드의 예상 번호가 같다는 것은 현재 라운드에서 대결을 했다는 것이다. 예를 들면 3번과 4번 중에 3번이 이겼다면 다음라운드에 2번이 되고 4번이 이겼어도 2번이 된다.

이런 방식으로 계속 대결을 해나갈때 a,b가 몇 라운드에 대결하게 되는지 구하는 것이다.

위에서 라운드 번호 규칙을 이용해서 알고리즘을 만들면 다음과 같다.

1. a, b의 다음 라운드 번호를 미리 구한다. a의 다음라운드 번호 = a를 2로 나눈 몫 + a를 2로 나눈 나머지, b의 다음 라운드 번호 = b를 2로 나눈 몫 + b를 2로 나눈 나머지

2. 다음 라운드의 a, b 번호를 비교하여 같지 않다면 라운드 값을 하나 증가한다. 그리고 1번으로 돌아간다.

만약 다음 라운드의 a, b 번호를 비교하여 같다면 a, b는 현재 라운드에서 대결을 한 것이다. 라운드 값을 증가하지 않는다. 그리고 1번으로 돌아가지 않고 반복문을 종료한다.

코드

def next_round_number(a,b):
    next = [a//2+a%2, b//2+b%2]

    return next

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

    next_number = next_round_number(a,b)

    while True:
        if next_number[0] == next_number[1]:
            break
        answer+=1

        next_number= next_round_number(next_number[0], next_number[1])

    return answer