[2025.02.19] 예상 대진표

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 투너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고 1번↔2번, 3번↔4번, ..., N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번ㅇ르 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

 

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 랑누드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

 

 

제한사항

• N : 2^1이상 2^20 이하인 자연수(2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A !=B 입니다.)

 

 

입출력 예

N			A	B	answer
8			4	7	3

 

 

문제 풀이

풀이 언어 : C++

int solution(int n, int a, int b)
{
    int answer = 0;
    
    // 한 명이 남을 때까지 반복
    while(n!=1)
    {
        answer++; // 라운드 업데이트
        
        // a와 b가 만난다면
        if((a%2==0&&a-1==b)||(b%2==0&&b-1==a))
        {
            break; // 반복 종료
        }
        
        else
        {
            // a 업데이트
            if(a%2==0) a/=2;
            else a=(a+1)/2;
            
            // b 업데이트
            if(b%2==0) b/=2;
            else b=(b+1)/2;
        }
        
        n/=2; // 다음 라운드 인원 절반
    }

    return answer;
}

벡터를 추가하고 데이터를 많이 다루어야겠다는 생각을 초반에는 했는데 생각해보니 그럴 필요가 전혀 없는 문제였다. 오직 가지고 있는 매개변수 만으로도 충분히 풀 수 있는 문제였다.

 

최대 라운드는 n이 2의 m승일 때 m라운드이다. 그래서 처음엔 이 m을 구해서 반복문을 돌리려고 하였지만 다른 방법을 선택하였다. 어차피 반복문을 돌릴 것이라면 따로 횟수를 구하는 것이 아니라 한번 돌아갈 때마다 n을 2로 나누고 n이 1이 될 때까지 반복하는 방법이다. 이렇게하면 자연스럽게 m라운드까지 반복을 돌 수 있다.

 

N-1번과 N번이 서로 게임을 진행하고, 둘 중에 한 명이 다음 라운드로 올라가고, 다음 라운드로 올라간 사람은 다시 번호를 부여받고... 정말 많은 과정이 있지만 반복문 안에서는 그렇게 대단한 일은 일어나지 않는다.

먼저 라운드를 1을 더해서 업데이트를 해준다. a와 b가 대결을 붙던 붙지 않던 라운드는 카운트 해주어야 하기 때문에 다른 작업을 하기 전에 먼저 라운드 업데이트부터 진행한다.

그 다음 a와 b가 만났는지를 확인한다. 생각보다 만난다는 것을 표현하는 조건은 복잡하지 않다.

1. a가 짝수이면서 a-1이 b와 같을 때
2. b가 짝수이면서 b-1이 a와 같을 때

이 두 가지 조건이 바로 a와 b가 만난다는 조건이다. 이 조건을 생각해보려 토너먼트 그림을 그려보았다.

그림을 보면 결국 라운드를 올라가는 것과 상관없이 짝수인 수 N과 N-1이 토너먼트에서 만난다는 것을 알 수 있다. 예를 들면 4는 3과, 8은 7과 대결을 한다. a와 b중 누가 반드시 크다는 제한 사항이 존재하지 않기 때문에 a가 짝수면 a-1이 b, b가 짝수면 b-1이 a인 경우가 두 사람이 만나는 조건이다. 두 사람이 만났을 경우 그대로 반복을 종료하고 나와서 정답을 반환하면 된다.

 

하지만 만약 만나지 못했을 경우에는 a와 b의 값을 업데이트 해주어야 한다. 문제를 다시 한번 보자.

만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다.

이 부분을 구현해줄 것이다. 단 다른 번호들은 별로 관심 없다. a와 b만 이걸 적용해주면 된다.

a와 b는 서로 만날 때까지는 무조건 이기기 때문에 반드시 올라가야 한다. 이것도 짝수인지 홀수인지를 구분하여 처리해주면 금방 처리할 수 있다.

• 짝수인 경우 : 자기자신의 번호에서 나누기 2를 하여 업데이트
• 홀수인 경우 : 자기 자신의 번호에 1을 더하고 나누기 2를 하여 업데이트

a와 b 모두 위의 경우를 확인하고 자신의 수를 업데이트 한다.

 

마지막으로 n을 나누기 2로 업데이트 하고 다음 반복으로 넘어간다. 이렇게 a와 b가 만날 때까지 반복문을 돌리고 정답을 리턴하면 된다.

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스