[BEAKJOON] 1057_토너먼트_C언어

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

풀이

처음에 생각한 아이디어!

처음에 참가자가 16명이면 배열을 전부 1로 초기화 한다. 그리고 1이 연속으로 2개 나오면 둘 중 하나는 1로 다음 라운드에 진출시키고 하나는 0으로 탈락시킨다. 그리고 지민이와 한수는 둘이 연속으로 나올때 까지 1로 다음 라운드에 진출시킨다. 그리고 지민이와 한수가 연속으로 나오면 반복문을 멈추고 해당 라운드수를 출력한다.

다음은 라운드 진행을 표현한 그림이다. 연속된 1이 두 개이면 둘 중 아무거나 진출시키며 지민이와 한수의 번호는 무조건 다음 라운드로 진출시킨다. 이 경우 최대 참가자 수가 10만이라 최악의 경우 10만*10만의 시간 복잡도로 2초를 만족하지 못 한다..

그래도 이렇게 설명하는 이유는?? 그냥...ㅋㅋ

다음 아이디어!!는..

문제 같이 풀던 친구가 힌트를 줘서 그렇게 풀었다..솔직히 내가 풀었다고 하기도 그런 문제이다.

다음 라운드로 진출하게되면 짝수는 /2씩 홀수는 /2 +1 되게된다.

Ex)

지민이는 아래와 같은 번호로 다음 라운드에 진출하게된다.

8 -> 4 -> 2 -> 1

한수는 아래 번호와 같이 다음 라운드로 진출하게된다.

9 -> 5 -> 3 -> 2

지민이가 1, 한수가 2이면 붙게된다.

여기서 중요한건 홀수일 때 (n+1)/2를 하던 n/2+1을 해주어야 된다는 것과 /2연산을하면 0이되어 0일경우 1로 바꾸어주어야 한다는 것이다.

제출한 코드

#include <stdio.h>
int t, a, b, num;
 
int main()
{
    scanf("%d %d %d",&num, &a, &b);
 
    while (1)
    {
        if (a % 2 == 1 && a != 1) a++;
        if (b % 2 == 1 && b != 1) b++;
        if (a == 0)a = 1;
        if (b == 0)b = 1;
 
        if (a - b == 1 || b - a == 1 || a == b)
        {
            printf("%d", t + 1);
            return 0;
        }
        a /= 2;
        b /= 2;
        t++;
    }
    return 0;
}