[C++] 백준 1057번 토너먼트

1. 문제이해

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

1057번: 토너먼트

 

N명이 참가하는 토너먼트에서, 지민이와 한수의 번호가 주어진다.

번호는 앞에서부터 차례로 부여되며, 지민이와 한수는 서로 만나기 전까지 계속 이긴다.

이때, 지민이와 한수가 처음으로 만나는 라운드는 몇라운드인지 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

N명이 참가하는 토너먼트에서, 지민이와 한수가 처음으로 만나는 라운드를 구하는 문제이다.

토너먼트 형식은,

복수의 참가자를 1:1로 배치하여 패자는 바로 탈락하고 승자는 다른 경기의 승자와 대결하는 방식으로,

앞에서부터 두 명씩 짝지어 승자를 정해나가는 형식이다.

 

출처 : 나무위키

 

문제의 예제 1에서, 지민이의 위치가 1, 한수의 위치가 2인 경우에는

바로 둘이 먼저 승부를 겨루기때문에 1라운드에서 만나게 된다.

 

문제의 예제 2에서는, 지민이의 위치가 8, 한수의 위치가 9인 경우이다.

두 수가 인접한 경우라 바로 만날 것 같지만, 사실 그렇지 않다.

아래의 그림을 보자.

 

그림에서 보다시피, 지민이와 한수는 인접했음에도 불구하고,

4라운드에서 처음으로 만나게 된다.

 

그렇다면, 지민이와 한수가 처음으로 만나는 지점은 어떻게 도출해야 할까?

위의 그림을 다시 자세히 보면, (보라색 글씨를 유심히 보자)

처음 1라운드의 1, 2 번 중 한명이 올라가면, 그 사람은 자동적으로 다음 차례의 1번이 된다.

3, 4번 중 한명이 올라가면, 그 사람은 자동적으로 다음 차례의 2번이 된다.

지민이와 한수의 경우에는, 다음 차례에 자동적으로 4번, 5번이 된다.

 

즉, 둘 중 어느 한명이 올라가더라도 동일한 차례의 값이 나와야 한다.

그리고 이 값은 두 숫자를 2로 나눈 뒤 올림(ceil)해준 값과 같다.

따라서, 지민이와 한수의 위치 값을 2로 나눠준 뒤 올림해준 값이 같아질때까지

위와 같은 과정을 반복하면 되는 것이다.

 

이것을 위의 예제 2에 동일하게 적용해보면,

 

1라운드 :

지민이의 위치  = 8

한수의 위치 = 9

 

2라운드 :

지민이의 위치  = ceil(8/2) = 4

한수의 위치 = ceil(9/2) = ceil(4.5) = 5

 

3라운드 :

지민이의 위치  = ceil(4/2) = 2

한수의 위치  = ceil(5/2) = ceil(2.5) = 3

 

4라운드 :

지민이의 위치  = ceil(2/2) = 1

한수의 위치  = ceil(3/2) = 1

 

4라운드에서 둘의 위치가 동일해지므로, 처음 만나게 된다.

 

여기서 추가적으로 주의해야 할 점은,

지민이와 한수의 위치를 int형으로 놓으면 안된다는 것이다.

지민이와 한수의 위치를 int형으로 놓게 되면,

나눈 값 또한 정수형으로 나오기 때문에 올바른 값을 도출할 수 없게 된다.

(예를 들어, ceil(5/2) = ceil(2) = 2가 나오게 된다.)

필자는 double형으로 지민이와 한수의 위치를 저장해주었다.

 

 

 

3. 소스코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int N;	// 참가자 수
	double jimin;	// 지민이의 위치
	double hansoo;	// 한수의 위치
	int round = 0;	// 라운드 번호

	cin >> N >> jimin >> hansoo;

	while (jimin != hansoo) {
		jimin = ceil(jimin / 2);  // 현재 지민이의 위치 나누기 2, 올림
		hansoo = ceil(hansoo / 2);  // 현재 한수의 위치 나누기 2, 올림
		round++;
	}

	cout << round;

	return 0;
}

장황한 설명에 비해 코드는 비교적 간단하다.🤣

참가자 수와 지민이, 한수의 위치를 입력받은 후,

지민이와 한수의 위치가 같아질 때까지 위와 같은 연산을 반복하면 된다.

(다음 라운드의 위치 = ceil(현재 라운드의 위치 / 2))

 

또한, 위의 연산을 한번씩 수행할때만다,

round++로 현재 몇 라운드인지도 카운트 해주었다.

 

 

---

다른 분들의 코드를 보고 오니, 나누기 연산 후, 나머지 연산자까지 사용해

정확한 위치를 구하시는 분들도 많이 계셨다.

역시.. 다른 사람들 코딩도 많이 봐둬야 한발 더 나아가는 공부가 되는 듯하다.

오늘부터 또 다른 일주일인 월요일의 시작이다..😱

다음주면 추석이니까 그때까지 조금만 더 힘내자💪💪