[BOJ] 1057번: 토너먼트

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

 

 

 

문제

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

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

 

풀이

로직은 간단하다. 만약 김지민과 임한수의 번호 차이가 1이면서, 더 큰 번호가 짝수라면 해당 라운드를 출력한다.

(ex) 7번과 8번, 4번과 3번) -------- 4번과 5번, 6번과 7번처럼 더 큰 수가 홀수라면 만나지 않음

 

번호 차이가 1이 아닐 때는: 번호가 홀수라면 1을 더한 후 나누기 2, 짝수라면 그대로 나누기 2를 한다.

def new_number(n):
    if n % 2 == 0:
        return n // 2
    else:
        return (n + 1) // 2
    
N, kim, lim = map(int, input().split())
round = 1

while N > 1:
    if abs(kim - lim) == 1 and max(kim, lim) % 2 == 0: break

    kim = new_number(kim)
    lim = new_number(lim)
    N //= 2

    round += 1

print(round)

 

문제 조건 중 둘이 만나지 않는 경우에는 -1이라는 말이 있어서 처음에는 별 생각을 안하고 이것을 코드로 작성했는데, 생각해보니 둘이 만나지 않는 경우는 없었다. 어떻게든 최후의 2인으로서 도달할 것이기 때문이다. (둘이 만나기 전까지 계속 이긴다는 조건때문에!!) 

 

아무튼 실버치고 어려운 문제는 아니었던 것 같다.