[BOJ] 백준 1057 토너먼트

출처: https://www.acmicpc.net/problem/1057

Approach

총 16 라운드, Kim: 8, Lim: 9 일 때

라운드 거듭될 때마다 부여되는 번호는 아래와 같다.

    Kim: 8 → 4 → 2 → 1 ▶ 1

    Lim: 9 → 5 → 3 → 2 ▶ 1

4번째 라운드에 만나게 되었는데,

둘 중 이긴자가 다음 라운드의 번호를 부여하게 된다.

 

수치상으로보면 라운드를 진행시켜면서 둘의 번호가 일치할 때, 만났다고 볼 수 있다.

▶ {다음 번호} = ({현재 번호} + 1) / 2

부여되는 번호가 일치할 때까지 반복하면 된다.

 

문제에서 Kim과 Lim에게 부여되는 번호는 N보다 작으므로 만나지 않는 경우(-1)는 없다.

---

#include <stdio.h>

int Lim, Kim, ans, round;

int main() 
{
	// freopen("input.txt", "r", stdin);
	scanf("%d %d %d", &round, &Kim, &Lim);
	
	while (Kim != Lim) 
	{
		Kim = (Kim + 1) / 2;
		Lim = (Lim + 1) / 2;
		ans++;
	}
	
	printf("%d\n", ans);
}