[백준 - C#] 1057번 토너먼트

문제링크

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

1057번: 토너먼트

 

문제

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

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

조건

시간제한 : 1초
메모리 제한 : 512 MB

입력

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

출력

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

 

문제정리

1. 번호는 1번부터 N번까지 입니다.
2. 라운드 마다 참가자가 홀수명이라면 마지막 번호 참가자는 부전승입니다.
3. 각 라운드 마다 승자들은 1번부터 번호를 순차적으로 다시 부여합니다.
4. 김지민과 임한수는 만나기 전까지 항상 이긴다.
5. 김지민과 임한수의 번호가 주어질 때 대결하는 라운드 번호 출력

이번 문제의 경우 김지민과 임한수의 번호가 주어질 때 둘이 만나는 라운드의 번호를 출력하는 문제입니다.

결국 다른 어떤 참가자가 이기던지 상관없이 김지민과 임한수의 번호만 파악하면 되는 문제입니다.

아래는 두번째 예제인 16 8 9의 입력을 그린 이미지 입니다.

김지민은 8이고 임한수는 9의 경우 값의 변화를 확인해보면

김지민 : 8 -> 4 -> 2 -> 1 

임한수 : 9 -> 5 -> 3 -> 2

의 값을 나타 낼수 있는데 즉 라운드가 증가할 때마다 (자기번호 + 1) / 2의 값으로 변환하는것을 확인해 볼 수 있습니다.

그리고 제일 중요한 둘이 만났다는 것을 아는 방법은 김지민과 임한수의 값이 같을 때 입니다.

예를들어 김지민은 3 임한수가 4일때 (3+1)/2 는 2이고 (4+1)/2 도 2이기 때문입니다.

 

아래 코드는 위에 이미지를 그대로 풀이한 것이며 서로 대결하지 않을 가능성으로 지민이와 임한수의 값이 라운드의 번호보다 크다면으로 한번 확인하고 넘어갔습니다.

 

C# 코드

static void Main(string[] args)
{
    // 1057 토너먼트
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int kimNum = int.Parse(input[1]);
    int hanNum = int.Parse(input[2]);
 
    int roundNum = 0;
 
    if (kimNum > N || hanNum > N)
    {
        roundNum = -1;
    }
    else
    {
        // 두 값이 2로 나누었을 때 같으면 대전 상대 입니다.
        while (kimNum != hanNum)
        {
            // 라운드 올라갈때마다 번호 수정
            kimNum = (kimNum + 1) / 2;
            hanNum = (hanNum + 1) / 2;
            roundNum++;
        }
    }
 
    writer.WriteLine(roundNum);
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.