[백준 1057] 파이썬_토너먼트

https://www.acmicpc.net/problem/1057

1057번: 토너먼트

우리가 흔히 아는 토너먼트에서 서로가 몇 번만에 만나는지를 출력하는 문제이다.

 

접근 방법

다음 라운드로 진출하는 참가자는 다시 왼쪽부터 1번, 2번.. 순으로 받는다. 

즉, (1 2) (3 4) (5 6) (7 8) (9 10) 이렇게 5개의 조가 있을 때 다음 라운드에 받는 번호는 2/2, 4/2, 6/2, 8/4와 같이 변한다.

또한 연속된 수에서 홀수가 작은 수여야만 만날 수 있다.

 

1. 서로 번호의 차이가 1이고
2. 작은 수가 홀수이면 토너먼트 횟수 출력
3. 그렇지 않다면 짝수는 //2로 변하고, 홀수는 (홀수+1)//2로 변한다.

N, a, b = map(int, input().split()) # a,b = 1라운드 번호

cnt = 1 # 반복 횟수

while True:
    # 만나는 조건
    # 가지고 있는 번호가 동일하고 
    if a<b:
        if (a+1 == b) and (a//2 == b//2 -1):
            print(cnt)
            break
    else:
        if (b+1 ==a) and (b//2 == a//2-1):
            print(cnt)
            break
    if a % 2:
        a = (a+1)//2
    else:
        a = a//2
    if b % 2:
        b = (b+1)//2
    else:

        b = b//2
    #print(a)

    cnt =cnt+1

N, a, b = map(int, input().split()) # a,b = 1라운드 번호


cnt = 1 # 반복문 횟수


while True:
    if a<b:
        if (a+1 == b) and a%2 ==1:
            print(cnt)
            break
    else:
        if (b+1 ==a) and b%2 == 1:
            print(cnt)
            break
    if a % 2:
        a = (a+1)//2
    else:
        a = a//2
    if b % 2:
        b = (b+1)//2
    else:

        b = b//2
    #print(a)

    cnt =cnt+1

 

(a//2 == b//2 -1) 코드를 단지 a%2 ==1로 바꾸어줄 수 있는데 연산의 수는 한 번에 2번씩 줄어들긴한다.

아직은 노가다식으로 풀어 시간에 관한 개념이 많이 없지만, 점점 배워가고 있다.

내일도 더 재밌는 알고리즘을 풀러가보자!