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

문제

---

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

풀이

---

 A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정했을 때, 두 참가자가 붙으려면 바로 옆의 참가자를 이겨야 한다. 따라서 A와 B가 서로 같은 조가 될 때까지 계속 나눠줘야 한다. 다만 값이 홀수인 경우는 해당 값에 1을 더한 경우와 같으므로, 홀수가 나올 때마다 1을 더해줘 짝수를 유지하며 A와 B가 붙을 때까지 반복한다.

#include <iostream>

using namespace std;

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

    int quotient_a = 0;
    int remainder_a = 0;
    int quotient_b = 0;
    int remainder_b = 0;
    int idx_a = a;
    int idx_b = b;

    while (1)
    {
        if (abs(idx_a - idx_b) <= 1)
        {
            if (max(idx_a, idx_b) % 2 == 0)
            {
                answer = cnt + 1;
                break;
            }
        }

        quotient_a = idx_a / 2;
        remainder_a = idx_a % 2;

        if (remainder_a != 0)
        {
            idx_a = quotient_a + 1;
        }

        else
        {
            idx_a = quotient_a;
        }

        quotient_b = idx_b / 2;
        remainder_b = idx_b % 2;

        if (remainder_b != 0)
        {
            idx_b = quotient_b + 1;
        }

        else
        {
            idx_b = quotient_b;
        }

        cnt++;

    }

    return answer;
}

이를 더 간단하게 표현한다면 아래와 같은 코드가 나온다.

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;
}