BOJ 1057 - 토너먼트 문제풀이

문제를 읽고 이해하기

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다.

 

이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다.

 

이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

 

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

 

입력

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

 

출력

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

 

재정의와 추상화

이 문제의 핵심은 위의 '문제를 읽고 이해하기'에서 두 번째 문단이다. 그중에서 핵심 중 핵심 문장은 아래와 같다.

다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다.

 

전체 참가자 수가 10이고, 1 라운드에서의 김지민의 번호와 임한수의 번호를 각각 8, 9라고 가정했을 때, 과정은 아래와 같다.

빨간색으로 표시된 부분이 다음 라운드에서의 인덱스가 부여되는 과정이다. 문제에서 말한 대로, 라운드가 바뀔 때마다 처음부터 참가자의 번호를 1번부터 매긴다고 하였으므로, 8과 9는 각각 2 라운드에서 4와 5로, 4와 5는 3 라운드에서 2와 3으로 그림에서 보는 것과 같이 바뀐다.

 

이렇게 새로 인덱스가 매겨지는 원리는 다음과 같다.

 

인접한 번호끼리 각각 2개 씩 짝지어 대결한 후 다음 라운드로 진출하므로,

다음 인덱스 = 현재 인덱스 / 2 + 현재 인덱스 % 2 (나머지를 더해주는 이유는 홀수일 때는 +1을 해야하므로)이다.

이는, 다음 인덱스 = (현재 인덱스 + 1) / 2와 같다. (이는 자명한 사실이므로 굳이 설명하지 않겠음)

 

그렇게 라운드가 계속 진행될 때마다 라운드 수를 증가시키고, 그러다가 김지민과 임한수가 서로 대결하는 라운드가 오는 경우 종료한다.

종료하는 원리는 위에서 설명한 것과 같이, '현재 라운드의 인덱스를 이용해 구한 다음 라운드에서 서로의 인덱스가 서로 같으면(위 예제에서는 1로 같다)' 종료하게 만들면 된다.

 

코드 작성

#include <iostream>
#include <algorithm>
using namespace std;

int n, kim, lim;

int bp() {
    int round = 1;
    while (n) {
        if ((kim + 1) / 2 == (lim + 1) / 2)
            break;

        kim = (kim + 1) / 2;
        lim = (lim + 1) / 2;
        round++;
        n /= 2;
    }
    if (!n)
        return -1;
    return round;
}

int main() {
    cin >> n >> kim >> lim;
    cout << bp();

    return 0;
}

 

회고하기

수학적 사고력이 떨어지는 나는 처음 딱 이 문제를 보았을 때 감이 잡히지 않았기에, 테스트 케이스에 있는대로 김지민의 번호를 8, 임한수의 번호를 9로 하여 N이 9인 것부터 17인 것까지 직접 과정을 관찰하며 규칙성을 찾고자 했다.

 

그렇게 나름대로 찾은 규칙성으로 코드를 짜보았지만, 테스트 케이스는 똑바로 나왔기에 '맞았다'고 생각했었다. 그러나 결과는 실패!

 

그러다가 구글신을 통해 다른 사람이 짠 코드를 보았는데, 그 코드는 뭔가 내 코드와는 다르게 '정돈'되어 있으며, 결과를 도출해내는 코드가 '모든 경우에서 무조건 성립할 것'임이 자명한 코드였다. 그러나 나는 코드를 고안하는 과정에서 모든 경우에서 꼭 성립할 것이라는 것은 증명해내지 못했다는 것을 깨달았다. 안좋게 말하면, '끼워맞춘' 셈..

 

물론 구글신의 힘을 빌렸기 때문에 내 힘으로 문제를 온전히 풀어내지는 못했지만, 수학 분류의 알고리즘 풀이에 있어서 배운 점은 많은 문제였다.