백준 1057번 - 토너먼트

https://www.acmicpc.net/problem/1057

1부터 N까지 번호가 있을 때

주어진 두 수가 몇 번째에 만나는지 구하면 된다.

큐를 이용해서 두 명씩 뽑은 다음에 지민이와 한수가 두 명에 포함되면 바로 나오고

그렇지 않은 경우에는 두 명중에 한 명만 큐에 포함시켜서 다음 라운드로 갈 수 있게 했다.

큐를 사용한 이유는 1번부터 차례대로 확인할 수 있도록 하기 위해서다.

이때, 지민이가 왼쪽에 있거나 오른쪽에 있으면 지민이를 포함시키고

한수가 왼쪽에 있거나 오른쪽에 있으면 한수를 포함시킨다.

만약 둘다 없으면 그냥 아무나 올려도 되는데 오른쪽을  올려주도록 했다.

다음 라운드로 올라가도록 하기 위해

새로운 큐를 더 생성해서 기존 큐의 1/2씩 포함시키고 이것을 다시 기존의 큐로 대입하여

기존 큐의 크기가 1보다 클 때 까지 진행했다.

큐의 사이즈가 1이면 만나지 않았다는 것이기 때문이다.

#include <iostream>
#include <queue>
using namespace std;
 
 
int main(){
    
    int n,p1,p2;
    cin>>n>>p1>>p2;
    
    queue<int> q,q2;
    for(int i=1;i<=n;i++)
        q.push(i);
    
    
    int ans=0; //몇 번째에서 만나는지
    bool check=false; //지민과 한수 만나는지
    
    while(q.size()>1){
        ans++;
        queue<int> q2;
        
        int left=0,right=0; //왼쪽, 오른쪽 사람
        while(!q.empty()){
            
            if(q.size()==1){ //홀수 일 때
                q2.push(q.front());
                q.pop();
                break;
            }
            
            left=q.front();
            q.pop();
            right=q.front();
            q.pop();
            
            //지민과 한수 만나면
            if((left==p1&&right==p2)||(left==p2 && right==p1)){
                check=true;
                break;
            }
 
            //지민이와 한수 안만나면 left와 right중에 하나만 다음 라운드로
            if(left==p1 || left==p2)    q2.push(left); //왼쪽에 지민이나 한수 있을 때
            else    q2.push(right); //오른쪽에 지민이나 한수 있거나 모두 없을 때
            
        }
        
        //지민이와 한수 만나면 밖으로
        if(check)
            break;
 
        q=q2;
    }
    
    if(check)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    
    return 0;
}