1057.토너먼트

(*)이번에 풀어볼 문제는 백준의 1057 토너먼트이다. 시뮬레이션 분류파트에 있는 문제이다.

1057번: 토너먼트

시뮬레이션은 겉보기엔 쉬워보일 수 있고 이렇게 구현하면 되겠지라는 생각이 들지만

막상 구현을 해보라고하면 굉장히 헷갈리거나 손을 못대는 경우가 많다.

 

 

이번 문제를 푸는 키워드는 규칙성을 찾아내면 간단하게 풀 수 있다.

8명이 토너먼트에 참가했다고 가정하고 우리가 찾아야할 참가자 번호가 3, 5 라고 해보자.

이 때 3과 5의 변화를 알아보면 아래와 같다.

 행방을 살펴보면 3은 3 => 2 => 1로 순서가 변화되고 5는 5 => 3 => 2로 순서가 변화된다.

이 변화에서 규칙성을 수식을 확인해보면 x = x/2 + x%2가 된다. 그러므로 그냥 while문을 돌려주면 된다.

 

< Code 설명 >

#include <iostream>

using namespace std;

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	int cnt = 0;
	while (a!=b){ // 아래 수식대로면 최종적으로 둘이 같아짐
		a = a / 2 + a % 2;
		b = b / 2 + b % 2;
		cnt++;
	}
	cout << cnt << "\n";
	return 0;
}