[ 프로그래머스 예상 대진표 (Lv2) ] (C++)

프로그래머스의 예상대진표(Lv2) 문제이다.

 

[ 문제풀이 ]

게임대회에 참가하는 총 인원의 수와 A번 참가자와 B번 참가자가 몇 번째 라운드에서 붙게되는지 구해야 하는 문제이다.

먼저, 한 라운드에서 참가자가 만나게 되기 위한 조건부터 정답을 도출하는 과정까지 진행해보자.

 

#1. 참가자가 라운드에서 만나게 될 조건

참가자가 라운드에서 만나기 위한 조건부터 확인해보자.

1라운드에서는 1번과 2번, 3번과 4번, 5번과 6번... 이런식으로 참가자들이 대결을  펼치게 될 것이다.

즉 ! 하나의 라운드에서 만나는 2개의 참가자의 번호는 "홀수번 한명과 짝수번 한명" 이 만나게 된다고 생각할 수 있다.

그런데 ! 한 가지 조건이 더 필요하다.

바로, "홀수번 참가자의 번호가 반드시 더 작아야 한다는 것" 이다.

1라운드에서 [ 1번 vs 2번 ] , [ 3번 vs 4번 ] , [ 5번 vs 6번 ] .... 이렇게 붙듯이, 반드시 "홀수번 참가자의 번호가 짝수번 참가자의 번호에 비해서 더 작은 번호"를 가지게 되는 것이다.

[ 2번 vs 3번 ] 같은 경우도, "홀수번 참가자 한명과 짝수번 참가자 한명이 붙는 경우" 가 될 수 있지만, 이 경우에는 홀수번 참가자의 번호가 짝수번 참가자의 번호보다 더 크기 때문에 이렇게 2명의 참가자는 라운드에서 만나지 않는다.

 

정리해보자. 하나의 라운드에서 만나는 2명의 참가자의 번호에는 다음과 같은 특징이 있다.

1. 홀수번 참가자 한명과 짝수번 참가자 한명이 하나의 라운드에서 만나게 된다.
2. 홀수번 참가자의 번호 = 짝수번 참가자의 번호 - 1 이여야만 한다.

위와 같이 정리를 할 수 있다.

 

#2. 라운드 별, 참가자의 번호 변경

라운드가 올라갈 수록 참가자들의 번호는 바뀌게 된다.

예를 들어서 1라운드에서 [ 1번 vs 2번 ] 이 붙었을 때, 누가 승리하든 그 다음 라운드에 진출하는 사람은 '1번'의 번호를 가지게 된다.

그럼 몇 가지 예시를 한번 나열해보자.

[ 1번 vs 2번 ] - 1번

[ 3번 vs 4번 ] - 2번

[ 5번 vs 6번 ] - 3번

[ 7번 vs 8번 ] - 4번

위의 예시는 해당 참가자들이 "그 다음 라운드에서 가지게 되는 번호" 를 적은 것이다.

1번과 2번이 붙었을 때, 누가 승리하든 그 다음 라운드에 진출하는 사람은 1번의 번호를 가지게 된다.

3번과 4번이 붙었을 때, 누가 승리하든 그 다음 라운드에 진출하는 사람은 2번의 번호를 가지게 된다.

여기서 ! 그 다음 라운드에서 가지게 되는 번호를 구하는 방법에 대해서 생각을 해보자.

바로, "해당 라운드의 짝수 번호 / 2" 를 한 결과값이 그 다음 라운드에서의 번호가 되는 것이다.

[ 1번 vs 2번 ] 에서 짝수번호는 '2번'이 되고, 그 다음 라운드에서의 번호는 2 / 2 = 1 번이 되는 것이다.

[ 5번 vs 6번 ] 에서 짝수번호는 '6번'이 되고, 그 다음 라운드에서의 번호는 6 / 2 = 3 번이 되는 것이다.

 

하지만 ! 라운드에서 붙은 사람들 중에서 굳이 짝수번호를 따로 찾아내어서 / 2를 하는 과정을 진행할 필요는 없다.

정말 단순하게 다음과 같이 계산할 수 있다.

"( 참가자의 번호 + 1 ) / 2 " 가 그 다음 라운드에서의 번호이다.

[ 1번 vs 2번 ] 에서 1번이 승리했다고 가정해보자. 그 다음 라운드에서의 번호는 (1 + 1 ) / 2 = 1 이 된다.

[ 1번 vs 2번 ] 에서 2번이 승리했다고 가정해보자. 그 다음 라운드에서의 번호는 (2 + 1) / 2 = 1 이 된다.

[ 7번 vs 8번 ] 에서 7번이 승리했다고 가정해보자. 그 다음 라운드에서의 번호는 (7 + 1) / 2 = 4 가 된다.

[ 7번 vs 8번 ] 에서 8번이 승리했다고 가정해보자. 그 다음 라운드에서의 번호는 (8 + 1) / 2 = 4 가 된다.

 

#3. 정답 도출

이제 모든 과정이 다 끝났다. A와 B가 몇 라운드에서 만나는지만 알아내면 된다.

우리는, A와 B가 각각의 라운드를 진행하면서 각 라운드에서 몇 번의 참가 번호를 가지게 되는지는 #2에서 알아보았고, 그리고 A와 B가 만나기 위한 조건은 #1에서 알아보았다. 즉 ! 모든 과정을 우리는 다 알고 있다.

이론적으로는 더 이상 설명할 내용이 없으니 소스코드를 확인해보자.

 int answer = 1;
 int Left = Min(a, b);
 int Right = Max(a, b);
    
 while(1)
 {
     if(Left % 2 == 1 && Left + 1 == Right) break;
     Left = (Left + 1) / 2;
     Right = (Right + 1) / 2;
     answer++;
 }

위의 코드에서 Left와 Right가 'A'와 'B'번 선수라고 생각하면 된다.

while문 안에서 조건문은 #1에서 했던 "2명의 선수가 하나의 라운드에서 만나기 위한 조건" 을 의미한다.

실제로, 두 선수가 만나게 되면 더 이상의 탐색을 그만하고 종료한다는 것을 확인할ㅇ 수 있다.

while문 안에서 Left와 Right의 값이 바뀌는 과정은 #2에서 이야기했던 "라운드가 진행됨에 따라, 참가자들의 바뀌는 번호"를 계산해주는 과정이다.

 

[ 소스코드 ]

using namespace std;
 
int Min(int A, int B) { return A < B ? A : B ; }
int Max(int A, int B) { return A > B ? A : B ; }
 
int solution(int n, int a, int b)
{
    int answer = 1;
    int Left = Min(a, b);
    int Right = Max(a, b);
    
    while(1)
    {
        if(Left % 2 == 1 && Left + 1 == Right) break;
        Left = (Left + 1) / 2;
        Right = (Right + 1) / 2;
        answer++;
    }
    return answer;
}