[BOJ1057] 토너먼트

[BOJ1057] 토너먼트

BOJ 토너먼트 문제 링크

문제 설명

1. N명이 토너먼트 대결을 펼친다.
2. 순서대로 번호가 주어지고, 다음 토너먼트에서도 앞에서부터 순서대로 번호가 주어진다.
3. 김지민과 임한수가 참가한다고 할 때, 둘의 번호가 주어지고 몇 번째 토너먼트에서 만나는지 구하는 문제.

코드 리뷰

• 요즘 코딩테스트를 준비하면서 어렵고 까다로운 문제만 푼 것같아서 쉴 겸 정답률 50퍼센트 대에서 골라봤는데, 문제가 너무 간단했다.
• 그냥 처음 배정받은 번호가 짝수든 홀수든 다음 번호 N=N/2+N%2 공식이 나온다.
• 임한수랑 김지민 다음 번호를 공식을 통해 구해나가다가 둘이 번호 같아질 때 카운트 값 출력하면 끝.
• N이 최대 100000 이지만, 반 토막씩 줄어드니깐 O(logN)안에 끝난다.

/* BOJ 1057번 토너먼트*/

#include <iostream>
using namespace std;

int main() {
	int N, kim, lim;
	cin >> N >> kim >> lim;
	int cnt = 0;
	while (kim != lim) {
		kim = kim / 2 + kim % 2;
		lim = lim / 2 + lim % 2;
		cnt++;
	}
	cout << cnt << endl;
	return 0;
}