C++ / 프로그래머스 / 예상 대진표

문제

 

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

코딩테스트 연습 - 예상 대진표

문제풀이

 

A가 B보다 항상 작다는 조건이 없어서 A가 B보다 클 경우 swap을 했다.

대진표에서 A가 번호가 작으므로 B와 붙을 경우 왼쪽에 A 오른쪽에 B가 된다.

따라서 만나는 경우에는 A를 2로 나눈 나머지가 1, A+1은 B인 경우밖에 없다.

 

a, b가 홀수인 경우에는 +1을 하고 2로 나누고, 그 외에는 그냥 2로 나눈다.

1,2가 붙고 3, 4가 붙는데 1/2와 2/2는 몫이 다르기 때문에 홀수의 경우는 +1을 해야 한다.

코드

#include <algorithm>
using namespace std;

int solution(int n, int a, int b)
{
    int idx(1);

    if (a > b) {
        swap(a, b);
    }

    while (1) {
        if (a % 2 == 1 && a + 1 == b) {
            return idx;
        }
        if (a % 2 == 1) {
            a++;
        }
        if (b % 2 == 1) {
            b++;
        }
        a /= 2;
        b /= 2;
        ++idx;
    }
}