1057)토너먼트

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

토너먼트에 참가하는 사람 두 명을 지정해주면 그 두 사람이 몇 라운드에서 만나는가를 찾아야 한다.

시뮬레이션 문제라 토너먼트 상황과 비슷하게 문제를 풀었다.

우선 사람 수만큼 배열을 할당하고 지정된 두 사람의 인덱스에 TARGET을 저장한다.

아래 과정은 토너먼트의 각 라운드에 참여하는 사람들의 수가 홀수이냐 짝수이냐에 따라 차이가 있다.

배열을 순차적으로 두 개씩 비교해 두 개 모두가 TARGET이면 그때 라운드 수를 반환하고

하나만 TARGET일 때 임시 인덱스 위치에 TARGET을 저장하고 임시 인덱스를 하나 증가시킨다.

둘다 TARGET이 아니면 임시 인덱스 위치에 NON_TARGET을 저장하고 임시 인덱스를 하나 증가시킨다.

#include<stdio.h>
#define TARGET 1
#define NON_TARGET 0
 
int main() {
    int N;
    int target1, target2;
    int t = 0;
    int *tournament;
    int isMatching = 0;
    int count = 0;
 
    scanf("%d %d %d",&N,&target1,&target2);
    tournament = (int *)calloc(N,sizeof(int));
    tournament[target1 - 1] = TARGET;
    tournament[target2 - 1] = TARGET;
 
    
 
    while (!isMatching) {
        count++;
 
        if (N % 2 != 0) {
            for (int i = 0; i < N-1; i += 2) {
                if (tournament[i] + tournament[i + 1] == 2) { //hit
                    isMatching = 1;
                    break;
                }
                else if (tournament[i] + tournament[i + 1] == 1) tournament[t++] = TARGET;
                else tournament[t++] = NON_TARGET;
 
            }
            tournament[t] = tournament[N - 1];
            N = N / 2 + 1;
        }
        else {
            for (int i = 0; i < N; i += 2) {
                if (tournament[i] + tournament[i + 1] == 2) { //hit
                    isMatching = 1;
                    break;
                }
                else if (tournament[i] + tournament[i + 1] == 1) tournament[t++] = TARGET;
                else tournament[t++] = NON_TARGET;
 
            }
            N /= 2;
        }
        
        t = 0;
    }
    printf("%d\n",count);
 
    system("pause");
    return 0;
}

더 쉬운 방법도 있다.

지정된 참가자가 서로 만나기 전까지 항상 이기면서

다음 라운드에 올라갈 때 번호가 순서대로 다시 부여된다.

지정된 참가자의 번호가 다음 라운드로 올라갔을 때 다시 부여된 사이의 관계는 T2=(T1+1/)2이다.

이것을 이용해서 문제를 풀면 더 쉽게 풀 수 있다.