[백준 알고리즘][파이썬/Python] 1057번: 토너먼트

문제

시간 제한 : 1초, 메모리 제한 : 128 MB

 

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

 

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

 

 

출력

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

 

입출력 예

 

제출 코드

def go_up(n):
    if n % 2 == 0:
        return n // 2
    else:
        return n // 2 + 1

n, a, b = map(int, input().split())
# a : 김지민의 시작 번호, b : 임한수의 시작 번호
round = 1
while True:
    if abs(a-b) == 1 and (a//2 != b//2): # 맞붙게 되는 경우
        break
    else:
        a = go_up(a)
        b = go_up(b)
        round += 1
print(round)

문제의 핵심

# 1

김지민과 임한수가 대결하는 순간이 올 때, 그것을 인지할 수 있는 조건이 무엇인지 파악할 수 있어야 한다. 다양한 방법이 있겠으나 본인의 경우 다음과 같은 조건을 생각해봤다. 두 조건이 동시에 만족되어야 두 사람이 대결한다고 할 수 있다.

1. 새롭게 부여받은 두 사람의 번호의 차의 절댓값이 1이어야 한다.
2. 새롭게 부여 받은 두 사람의 각 번호를 2로 나누었을 때의 몫이 달라야 한다.

위 조건은 그림을 그려보면서 풀어보면 손쉽게 깨달을 수 있는 조건이다.

 

# 2

두 사람이 맞붙지 않게 될 경우, -1을 출력하라고 했는데 아무리 생각해봐도 둘이 대결하는 순간이 오지 않을 가능성은 없었다. 이걸 문제의 핵심이라고 해야 할지는 모르겠는데, 이것 때문에 이 상황 저 상황 고려해보면서 대진표를 그려봐도 둘은 결국 대결할 수밖에 없었다. 그래서 아몰랑 하고 -1을 출력하는 조건은 집어넣지도 않았다. 그래도 통과했다. 괜히 골머리를 앓았다고 생각해서 일단은 넣어봤다.

 

# 3

위 문제의 핵심과 비슷한 맥락이라면 비슷할 수 있는데, 처음 시작할 때 참가자 수가 홀수인 것도 딱히 고려할 필요가 없다. 문제를 풀어보면 그러하다. 이번 문제는 뭔가 고려해야 할 것만 같은 것들을 2개나 넣어서 괜히 사람을 신경 쓰이게 만든 것 같다. 혹은 내가 문제 제출자의 큰 뜻을 모르고 풀었는데 뽀록으로 맞았을 수도 있다.

 

라인 별 풀이

(1) line 1 ~ 5

김지민과 임한수는 서로가 대결하는 순간이 올 때까지 무조건 승리한다는 전제가 있다. 그러므로 항상 다음 라운드로 올라갈 것이고, 새로운 번호를 부여받게 될 것이다. 이 함수는 다음 라운드에 어떤 번호를 부여받을지 반환해주는 함수이다.

 

(2) line 11, 12

문제의 핵심 #1 에서도 언급했지만, 김지민과 임한수가 부여받은 번호를 통해 조건문을 살펴보고 조건문에 만족될 경우 서로가 대결하는 순간이므로 while문을 종료해준다.

 

(3) line 13 ~ 16

서로 맞붙는 경우가 아니라면 김지민과 임한수를 다음 라운드로 올리고, 그들의 번호를 새롭게 부여한다. 그리고 라운드의 횟수를 증가시켜준다.

 

 

 

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