알고리즘14 :: BOJ_1057_토너먼트

이 문제를 풀때 짝수, 홀수를 정확하게 찾아내고 싶어서 블로그들을 찾아봤는데, 이런 방법이 있었다.

 NUM = NUM / 2 + NUM % 2;

 

처음에 생각한 아이디어는 다음과 같다. 테스트케이스 16 8 9 의 경우

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16이면 

여기서 홀수 일경우 +1 을 더해준다.

2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16가 된다. 

여기서 /2 를 해주게 되면 다음 순번을 확인할 수 있게 된다.

1 2 3 4 5 6 7 8 여기서도 +1을 더해준다. 

2 2 4 4 6 6 8 8 

마찬가지로 /2를 해주게 되면 다음 순번을 확인할 수 있다.

1 2 3 4 

결국 이렇게 WINNER까지 올라가게 된다. 

이때 조건을 형성하여 반복문을 빠져나가도록 하였는데, 그 조건은

 

토너먼트는 반드시 오름차순으로 나오므로 입력받은 a는 b보다 작아야 한다. 

또한, a는 홀수가 되어야 하며 b는 짝수가 되어야 한다. a+1 == b는 성립해야 한다. 

마지막으로 b가 짝수이거나 a가 홀수인지를 체크해서 반복문을 탈출하도록 하였다.

탈출시 count를 증가시켜주는 이유는 round를 시작하기전에 처음에 만나게 되면 둘이 붙을 경우를 체크해주기 위함이다.

4 3 4 로 예를 들어볼 수 있다.

1 2 3 4 (3,4 에서 서로 맞붙게 되므로 값은 1이 나와야 한다.)

 

찾아본 바는 두가지 방법이 있었는데 첫방법이 굉장히 인상적이어서 이 방법을 써도 좋을듯 싶다.

 

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n,a,b, count=0;
    cin>>n>>a>>b;
    
    while(a!=b){
        
        if(a<b && b%2==0 && (a+1)==b){
            count+=1;
            break;
        }
        if(a%2!=0 || b%2!=0){
            a = a%2 ==0 ? a:(a+1);
            b = b%2 ==0 ? b:(b+1);
        }
        
        a/=2;
        b/=2;
        
        count+=1;
        
    }
    cout<<count<<endl;
}