[Lv 2] 예상 대진표

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

프로그래머스

 

이 문제는 a와 b값이 짝수인 경우 2로 나누고 홀수 인 경우 1을 더한 후 2로 나누면 해결할 수 있다.

이유는 12 34 56 이렇게 짝이 이루어지는데 짝이 맞아졌을 때 이긴 대상은 다음라운드에서 N/2번째 숫자가 되기 때문이다.

따라서 2가 이길경우 1이되고 1이 이길경우 1이 되기 위해서는 위 방식을 사용해야한다.

 

이 방식이 해결방안이 될 수 있는 이유는 a와 b는 반드시 다음 라운드에 진출하기 때문에 만날때 까지 나누면 되기 때문이다.

만나기 위해서 주의해야할 상황중 하나는 2와 3같이 1차이지만 2로 나눴을때 같은 값이 되는 경우는 만나지 않는 경우로 판단해야한다.

 

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

int solution(int n, int a, int b)
{
    int answer = 1;
 
    
    while(abs(a-b)!=1||a/2==b/2){
        if(a%2==0)
            a/=2;
        else{
            a++;
            a/=2;
        }
        if(b%2==0)
            b/=2;
        else{
            b++;
            b/=2;
        }
        answer++;  
    }

    return answer;
}