토너먼트

Created

2021/10/12 07:47

문제 번호

1057

카테고리

수학

브루트포스

1057번: 토너먼트

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다.

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

Memo

트리 구조를 떠올려 라운드 수를 먼저 세봄

2^n

명의 참가자가 있을 때,

n

이 곧 라운드 수가 되므로 전체 참가자 수를 반으로 나눠가는 식으로 반복문을 돌려서 라운드 카운트를 측정함

서로 만났는지 확인을 일일이 해도 좋겠지만, kim의 현재 번호를 통해 다음 라운드의 매칭 순서와 lim의 현재 번호를 통해 다음 라운드의 매칭 순서를 찾을 수 있다는 것을 알아냄

예를 들어 현재 번호가 1번 혹은 2번이라면, 다음 라운드의 매칭 순서는 무조건 1임

예를 들어 현재 번호가 3번 혹은 4번이라면, 다음 라운드의 매칭 순서는 무조건 2임

따라서

\frac{Current Number + 1} {2}

이 다음 라운드의 매칭 순서이므로, kim과 lim의 현재 번호로 유도한 다음 라운드의 매칭 순서가 동일하면 측정하고 있었던 라운드 카운트를 반환하게 함

단, 반복문을 모두 소진하여 나오는 경우에는 만나지 않은 것으로 생각하여 -1을 반환하게 함

Code

제출 날짜

@10/5/2021

메모리

2020 KB

시간

0 ms

#include <iostream>
#include <vector>

int						g_participants;
int						g_kim;
int						g_lim;
int						g_answer;

void	pre_setting(void)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

void	input_action(void)
{
	std::cin >> g_participants >> g_kim >> g_lim;
	g_answer = -1;
}

void	solution(void)
{
	int					count = 1;

	while (g_participants > 1)
	{
		++g_kim /= 2;
		++g_lim /= 2;
		if (g_kim == g_lim)
			break ;
		++count;
		g_participants /= 2;
	}
	if (g_participants >= 1)
		g_answer = count;
}

void	output_action(void)
{
	std::cout << g_answer;
}

int		main(void)
{
	pre_setting();
	input_action();
	solution();
	output_action();
	return (0);
}
C++
복사