[백준알고리즘] 1057번: 토너먼트 -C++

[백준알고리즘] 1057번: 토너먼트 -C++

1057번: 토너먼트 (acmicpc.net)

1057번: 토너먼트

김지민과 임현수가 만나는 라운드를 출력하는 문제다.

 

이 문제는 수학적으로 쉽기도 하고, 직접 구해도 풀 수 있는 문제다. 나는 여기서 직접 만나는 경우를 구했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

먼저, 앞서 수학적으로도 구할 수 있고, 직접 일일이 구할 수도 있다고 했다. 

 

수학적으로 구할 수 있는 방법은 다음과 같다. 현재 라운드에서 참가자의 번호가 \( N \) 일 때 다음 라운드에 진출하게 된다면 새롭게 받는 번호는 \( (N + 1) / 2\) 가 된다는 점을 이용하는 것이다.

이러한 것은 계산을 통해서 쉽게 구할 수도 있다. 참가자 1번과 2번의 대결 후 진출자는 무조건 1번을 받게 되고, 참가자 3번과 4번의 대결 후 진출자는 무조건 2번을 받게 된다. 이러한 것들의 규칙을 찾다 보면 +1과 2배가 금방 눈에 띈다.

 

실제로 많은 분들이 이런 연산을 통해서 문제를 해결한 것 같다.

 

그런데, 시간 제한을 보고는 직접 대결을 확인해도 통과할 수 있을 것 같아서 직접 해봤다. 간단히 참가자들의 참가 번호를 라운드 진출 때마다 새롭게 갱신하지 않고, 큐에 넣어서 대결을 확인했다.

만약, 김지민과 임한수가 동시에 큐에서 나온다면 둘이 대결하는 라운드를 찾게 되는 것이다. 그렇지 않고, 한 명만 나오게 된다면, 그 사람을 다음 라운드에 진출시키면 되고, 나오지 않는다면 임의의 한 명만 진출시키면 된다. 이런 과정을 반복하다 보면 결국에 만나는 라운드를 찾을 수 있다.

 

아래는 해당 로직으로 푼 코드다. 정말 간단한 로직을 사용했기 때문에 코드를 보는 데는 문제가 없을 것 같다.

#include <iostream>
#include <queue>
#include <set>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

int findRound(std::queue<int>& match, int kim, int im)
{
	int round = 0;

	while (1 < match.size())
	{
		int qLength = match.size();
		round++;

		int popCount = 0;
		while (popCount < qLength)
		{
			if (1 == qLength - popCount)
			{
				match.push(match.front()); match.pop();
				break;
			}

			popCount += 2;
			std::set<int> number;
			number.insert(match.front()); match.pop();
			number.insert(match.front()); match.pop();
			
			if (number.find(kim) != number.end() && number.find(im) != number.end())
				return round;

			if (number.find(kim) != number.end())
			{
				match.push(kim);
				continue;
			}

			if (number.find(im) != number.end())
			{
				match.push(im);
				continue;
			}

			match.push(*number.begin());
		}
	}

	return -1;
}

void solve(void)
{
	int n, kim, im;
	std::cin >> n >> kim >> im;

	std::queue<int> match;
	for (int i = 1; i <= n; i++)
		match.push(i);

	std::cout << findRound(match, kim, im);
}