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

문제

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

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

---

출력

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

---

 

예제 입력 1 복사

16 1 2

예제 출력 1 복사

1

예제 입력 2 복사

16 8 9

예제 출력 2 복사

4

예제 입력 3 복사

1000 20 31

예제 출력 3 복사

4

예제 입력 4 복사

65536 1000 35000

예제 출력 4 복사

16

예제 입력 5 복사

60000 101 891

예제 출력 5 복사

10

---

풀이과정

문제에서 토너먼트로 경기가 이루어지기때문에 경기에서 이기면 다음 번호는

(기존번호 / 2) = 다음번호 형식으로 진행이 되고 기존번호가 ( 번호(짝수) / 2 ) 이고 ( (번호(홀수) + 1) / 2로 진행이 되게된다.

이러한 형식으로 문제가 진행이 되고

토너먼트에 경우에는 1 2 는 바로 만나는 경기이지만 8 9 에 경우에는 7 vs 8 9 vs 10 으로 바로 만나지않는 경기로 진행이 된다.

그래서 이러한 부분도 신경을 써서 문제를 진행해야하는데.

나의 경우에는 쨋든 2명이 서로 만난다는 거는 번호의 차이가 1 이라는 것이고

예를 들어 1 vs 2 , 3 vs 4 , 5 vs 6 , 7 vs 8 , 9 vs 10 식으로 경기가 진행된다면 모든 경기는 큰 값이 짝수라는 특징이 있다. 그러므로

8과 9가 있다면 홀수가 더 큰 값이므로 만날 수 없는 경기라고 생각할 수 있다.

code

#include <iostream>
#include <algorithm>

int		main(void)
{
	int	n, k, l, count;

	std::cin >> n >> k >> l;
	count = 0;
	while (true)
	{
		count++;
		if (k - l == -1 || k - l == 1) 
			if (std::max(k, l) % 2 == 0)
				break;
		if (k % 2 != 0) k++;
		if (l % 2 != 0) l++;
		k = k / 2;
		l = l / 2;
	}
	std::cout << count;

	return (0);
}

---

후기

점점 더 좋은 코드를 구성하기위해서 코드짜는 습관이 바뀌어가는것이 보여서 마음에 든다.