1057. [Python]토너먼트

1. 문제

 

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

1057번: 토너먼트

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 512MB
• 규칙 찾아서 해결

 

3. 파이썬 코드

 

N,jimin,hansoo = map(int,input().split())
# 라운드 체크
round = 1
# N을 계속해서 나눠가기때문에 0이아닌경우 까지
while N != 0:
    # 지민이가 큰지 한수가 큰지 모르기 때문에 이런 조건 설정함
    if jimin > hansoo:
        # 한수가 홀수이고 지민이가 짝수인 경우 한수 +1 이 지민이인 경우
        if hansoo%2 == 1 and jimin%2 == 0:
            if hansoo+1 == jimin:
                print(round)
                break
    elif jimin < hansoo:
        # 지민이가 홀수이고 한수가 짝수인 경우 지민 +1 이 한수인 경우
        if jimin%2 == 1 and hansoo%2 == 0:
            if jimin+1 == hansoo:
                print(round)
                break
    else:
        # 둘다 같은경우 -1
        print(-1)
    # 만약 N이 홀수인 경우
    if N%2 == 1:
        # 나눈값에 +1 을해준다 맨마지막 인원은 계속 올라가기 때문에
        N = N//2 + 1
    else:
        N //= 2
    # 지민이가 홀수인 경우
    if jimin%2 == 1:
        # 나눈값에 +1을 해줘야한다.
        jimin = jimin//2 + 1
    elif jimin%2 == 0:
        jimin //= 2
    # 한수가 홀수인 경우
    if hansoo%2 == 1:
        # 나눈값에 +1을 해준다
        hansoo = hansoo//2 + 1
    elif hansoo%2 == 0:
        hansoo //= 2
    # 매 대결이 끝나면 라운드 +1 해준다.
    round += 1

 

4. 문제를 풀고난 후 생각

 

• 지민이와 한수중 누가 더 숫자가 큰지에 대해서 따로 얘기가 없기 때문에 한수가 클때와 지민이가 클때를 나눠서 조건을 설정해줬다.
• 문제에서는 1,2 중 1이 이기고 3,4 중 3 이이겨서 올라가더라도 라운드가 새로워 질때마다 앞에서부터 1,2,3,4 이런순으로 다시 번호를 붙이기 때문에 한수와 지민이가 속한 그룹의 번호가 몇번인지를 확인하는 방식으로 코드를 구현했다. 
  ex) 지민 => 8, 한수 =>9 이면 지민이는 4번째 그룹 한수는 5번째 그룹에 속해있으며 다음 라운드로 올라갈 경우 4, 5 라는 새로운 번호를 부여받게 되며 이를 반복해가며 현재 지민이의 점수가 더 낮기 때문에 지민이가 홀수인 경우 +1 한값이 한수와 같아질 경우 두 선수가 만나는 라운드가 된다.
• 2명씩 짝을 지어서 라운드당 게임을 하기 때문에 좀 더 작은 번호를 가진 선수에서 +1 한 값이 다른 선수와 같은경우 두 선수가 만나게 되는 라운드이며 매 라운드마다 선수들이 홀수인지 짝수인지 판단을 해주는 것이 필요하다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 규칙 찾기
• 브루트포스(?)