[C++] level2 예상대진표 12985

📌예상대진표

△△ 게임대회가 개최되었습니다. 이 대회는 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 : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

N = 8, A = 4, B = 7일 때 return answer = 3

📌풀이

주의할 점

1. 매 라운드마다 넘버링이 다시 1부터 됨
2. N-1번↔N번의 참가자끼리 게임을 진행

주의할 점을 고려하여 문제를 보았을 때, 먼저 각 라운드를 answer에 담자. 매 라운드는 n/2만큼 돔.

1R의 n이 8개면 -> 게임 4번 진행
2R의 n이 4개면 -> 게임 2번 진행 //n이 4개가 된 이유는 1R에서 우승자 4명 나오니까
3R의 n이 2개면 -> 게임 1번 진행 //게임 종료. !우승자 나옴!

그러고 1R을 돌렸을 때 다시 넘버링이 되면 다음과 같이 된다.

1-2 중 우승자는 1
3-4 중 우승자는 2
5-6 중 우승자는 3
7-8 중 우승자는 4

처음에는 while의 조건을 n이 1이 되면 종료되도록 하여 그 안에서 재넘버링하는 식으로 구현했는데, 효율적이지 않은 것 같았다. 굳이 모든 넘버를 고려하지 않고, 주어진 a, b만 고려해주면 되기 때문이다!

그래서 a와 b의 넘버만 라운드가 진행될 때마다 재넘버링 해주는 걸로 수정하였다.

📌코드

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

int nextNum(int num){ //숫자 다시 넘버링
    return num % 2 == 0 ? num / 2 : (num+1) / 2;
}

int solution(int n, int a, int b)
{
    int answer = 1; //각 라운드

    //a와 b는 서로 1개 차이, a와 b 중 큰 값이 2의 배수의 경우
    while(!(abs(a - b) == 1 && max(a, b) % 2 == 0)){
        a = nextNum(a);
        b = nextNum(b);
        answer++;
    }

    return answer;
}

더 나은 대안

비트연산자를 이용하여 문제를 푸셨다. 이런 접근을 하다니 충격적이다.

#include <iostream>
using namespace std;

int solution(int n, int a, int b) {
    int answer = 0;
    while(a != b){
        a = (a + 1) >> 1;
        b = (b + 1) >> 1;
        answer++;
    }
    return answer;
}

블로그에 풀이된 것을 보면 역시 마찬가지로 a와 b에 대해서만 네임을 재정리하셨다.
a와 b가 홀수인 것을 고려하여 +1을 해준 것 같고 2진수의 경우 (1,2,4,8,16.... //2의 배수로 증가)성질을 이용하여 비트를 오른쪽으로 시프트 해서 n/2(각 라운드)를 표현해준 것 같다.
충격적...!!!!!!......
비트연산자 공부해야지이.....

---

참고자료
https://mungto.tistory.com/205#recentComments //더 나은 대안