문제 12985. 예상 대진표

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2  

 

문제 요약 설명

게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이 때, 처음 라운드에서 A번을 가진 참가자가 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

입력

• 게임 참가자 수 N
• 참가자 번호 A
• 경쟁자 번호 B

입력 제한

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

입력 예제

// input(매개변수)
8 4 7 // N, A, B

// ans
3

 

풀이 방식

이진 탐색(Binary Search)을 사용하면 된다. 우선, log2(n)을 통해 최대 몇 번의 토너먼트(max_match)가 이루어 질 수 있는 지 찾고, 이진 탐색을 돌면서 a와 b가 중앙값을 기준으로 양 쪽을 갈랐을 때 같은 영역에 있는 지 확인한다. 만약 같은 영역에 있다면 A를 기준으로 이진 탐색을 하고, while문을 반복한 횟수를 저장하는 cnt를 1증가시켜준다. 그렇지 않다면 이진 탐색을 종료하고 max_match - cnt를 통해 answer를 구한다.

 

이렇게하면 문제가 풀리는 이유

해당 방식은 아래서부터 위로 만나는 과정을 구하는 것이 아닌, 위에서부터 아래로 만나는 과정을 구하는 방식이다. 즉, 결승에서 만나는지 확인하고, 부결승에서 만나는지, 8강에서 만나는지... 이런 식으로 구한다. 그렇기 때문에 while문이 종료되면 max_match에서 cnt를 빼는 것이다(결국 cnt는 결승부터 A와 B가 만나지 않은 횟수를 의미하게 된다.)

 

왜 기준이 양 쪽을 갈랐을 때 같은 영역에 있는 지인가?

해당 문제에서 이진 탐색방식으로 내려가면서 찾는 것은 이진 트리의 서브 트리로 반복적인 이동을 하는 것과 같다. 즉, 서브 트리로 이동하며 해당 위치에서 A와 B가 양쪽으로 갈라지는 경우는 해당 서브 트리의 왼쪽, 오른쪽 자식 노드일 경우밖에 없고(부모노드의 번호는 왼쪽 자식노드와 동일) 이 때 서로가 붙는다 판단 할 수 있다.

 

정답 코드 

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

int solution(int n, int a, int b)
{
    int answer = 0;

    int max_match = log2(n);
    
    int low = 1;
    int high = n;
    int mid = (low + high) / 2;
    int cnt = 0;
    
    while((a <= mid) == (b <= mid)){
       
        if(a <= mid){
            high = mid;
            mid = (low + high) / 2;
        }
        else{
            low = mid;
            mid = (low + high) / 2;
        }
        cnt++;
    }

    cout << max_match - cnt << '\n';
    answer = max_match - cnt;
    return answer;
}