2017 팁스타운 > 예상 대진표

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

1. 문제

△△ 게임대회가 개최되었습니다. 이 대회는 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 A B answer

8 4 7 3

- 입출력 예 설명

 입출력 예 #1

첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

2. 알고리즘

키워드 - 구현

N = 8, A = 4, B = 7 일때 A 와 B 는 항상 승리 한다.

토너먼트 이고 주어지는 숫자는 2의 지수승으로 온다는 것을 유의 하자.

Step 1.

N = 4, A = 2, B = 4 

N = 4 -> 8 / 2 = 4

A = 2 -> 4 / 2 = 2 4번째 인덱스에 있다가 토너먼트에 룰에 의해서 승리하면 앞쪽에 1,2 에 승리자와 붙게 된다. 1,2 승자는 1로 치환 되고 3,4의 승리자는 2로 치환 된다.

B = 7 -> 7 / 2 = 3 이지만 7 은 홀수 임으로 1을 더해 준다. 

총 8 명이 게임을 진행한다고 했을 때 아래와 같은 쌍이 만들어 진다.

[1,2] [3,4] [5,6] [7,8] 

각각의 승자들은

[1] [2] [3] [4] 의 새로운 대진표를 갖게 되는데 [7,8]의 승자는 [4]의 대진표를 얻게 된다. 

문제에서 주어진 조건인 A, B 는 항상 승리 하게 됨으로 [7,8] 의 승자는 7이고 대진표는 [4]를 얻게 된다.

Step 2.

위와 같은 방법으로 A, B 가 같지 않을 때까지 반복 하면 총 라운드 수를 구할 수 잇다.

3. 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <iostream> #include <sstream> #include <string> #include <algorithm> #include <functional> #include <vector> #include <list> #include <queue> #include <deque> #include <map> #include <set> #include <stack> #include <math.h> #include <memory.h> using namespace std;   #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #define ll long long   #define c_reverse(s) reverse(s.begin(), s.end()) #define c_sort(s) sort(s.begin(), s.end())   #define print_vector(v) for(int i=0; i<v.size(); i++) cout << v[i];   int solution(int n, int a, int b) {     int answer = 0;     int round = 0;     while (a != b) {         if (a % 2 == 0) {             a /= 2;         }         else {             a /= 2;             a++;         }           if (b % 2 == 0) {             b /= 2;         }         else {             b /= 2;             b++;         }         round++;     }     answer = round;     return answer; }   int main() {       cin.tie(0);     std::ios::sync_with_stdio(false);       solution(8, 4, 7);     return 0; } Colored by Color Scripter

cs