[프로그래머스] 예상 대진표

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

숫자 사이의 관계를 생각해보면 쉽게 해결할 수 있다.
n이 8, a는 3, b는 7인 경우를 생각해보자.

1번과 2번 중에서 승리하는 참가자는 1이 된다.
3번과 4번 중에서 승리하는 참가자는 2가 된다.
5번과 6번 중에서 승리하는 참가자는 3이 된다.
7번과 8번 중에서 승리하는 참가자는 4가 된다.

두 명 중 한명만 살아남기 때문에 라운드가 지나갈수록 참가자의 수는 절반으로 줄어들게 된다. 다음에 부여받는 숫자의 규칙을 찾아보면 i번째 참가자는 다음 라운드에서 i/2 + i%2번을 부여받음을 알 수 있다. 따라서 a와 b가 같은 번호를 부여받기 전까지 라운드를 진행하면 된다.

코드

#include <iostream>
using namespace std;

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

    while (a != b) {
        a = a / 2 + a % 2;
        b = b / 2 + b % 2;
        answer++;
    }
    return answer;
}