[Programmers/프로그래머스 lv2][C++] 예상 대진표

문제

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

프로그래머스 12985

 

문제 내용

N명의 참가자는 번호를 1~N번으로 부여받아 토너먼트 식으로 경기를 하게 된다.

매 라운드마다 (1,2), (3,4), ...., (N-1,N)이 토너먼트 경기를 하게 된다.

우리는 A번 참가자와 B번 참가자가 몇 라운드에 만나게 될지를 출력하면 된다. (그전까지 두 참가자는 항상 이긴다)

 

문제 풀이

프로그래머스 예상 대진표 풀이

위 그림은 각 라운드별로 어떤 참가자들이 겨루게 될지를 그려둔 것이다. (같은 조에 있으면 싸우게 된다.)

참가자는 항상 2의 지수승으로 주어져 부전승이 발생하지 않고, 2^20명까지 참가하니 라운드의 수는 최대 20까지 가능하게 된다.

우리는 입력받은 a와 b가 각 라운드별로 어떤 조에 배정받는지를 구하고, 같은 조에 배정받는 라운드를 구하면 된다.

 

코드

#include <iostream>

using namespace std;

int returnTeamNumber(int num,int pow){
    if(num%pow==0) return num/pow-1;
    else return num/pow;
}

int solution(int n, int a, int b)
{
    int pow=1;
    for(int round=1;round<=20;round++){
        pow*=2;
        
        if(returnTeamNumber(a,pow) == returnTeamNumber(b,pow)){
            return round;
        }
    }
}