[백준][1057][c++] 토너먼트

토너먼트 문제 링크

[내 풀이]
하나의 라운드에서 대결하는 사람들이 가진 번호의 특성은 작은 값이 홀수 이고 두 값 사이가 1차이가 난다는 점이다.

1) 지민과 한수의 번호를 오름차순으로 정렬한다
2) 작은 값이 홀수 이고 두 값 사이가 1차이가 나는지 확인
True -> stop
False -> 3)
3) 둘은 만나기 전까지 계속 이기기 때문에 다음 라운드에서 받게 되는 번호는
(현재 번호+1)/2이다
4) stop할 때 까지 2-3 반복!
하지만, 총 대결에 참가한 사람 수(N)가 정해져 있으니 반복은 log N까지만 할 수 있음

#include <iostream>

using namespace std;

int N;
int lower, higher;

int main() {
	int answer = 0;
	cin >> N;
	int first, second;
	cin >> first >> second;

	//오름 차순으로 번호 정렬
	if (first < second) {
		lower = first;
		higher = second;
	}
	else {
		lower = second;
		higher = first;
	}

	int n = 0; //대결 몇번 했는지 저장하는 변수
	//(1<<n)은 라운드에서 몇번의 대결이 일어났는지 reverse로 나타냄
	while ((1 << n) < N) {
		//작은 값이 홀수 이고 두 값 사이가 1이나면 대결하는 것임
		if (lower % 2 == 1 && lower + 1 == higher) {
			answer = n + 1;
			break;
		}
		lower = (lower + 1) / 2;
		higher = (higher + 1) / 2;
		n++;
	}

	cout << answer << "\n";
	return 0;
}

[총평]
쉬운 시뮬레이션 문제 였다.