백준 #1057 토너먼트

토너먼트 경기는 두개의 팀 또는 선수가 싸워서 이기면 한단계씩 올라가는 경기입니다.  기본적으로 이진트리 형태를 가지고 있습니다.

 

문제의 내용은, 1부터 N까지 선수들을 일렬로 세웠을 때, A번 선수와 B번 선수가 언제 경기를 하게 될 수 있는지를 찾는 것입니다.  이게 이진 트리라는 성격을 알면 의외로 쉽게 풀 수 있습니다.  Silver II 문제로 되어 있지만 그보다는 난이도는 너 낮다고 보입니다.

 

토너먼트

그림과 같은 토너먼트 표가 있다고 하고, 왼쪽부터 1, 2, 3, 4, 5, 6, 7, 8 이라고 숫자가 매겨졌다고 해보죠.  대한민국은 5번이 됩니다.  그런데 캐나다와는 언제 붙을 가능성이 있는지 알아보자고 한다면, 캐나다는 2번에 있습니다.  그러면 결승에 가서야 캐나다와 경기할 가능성이 있습니다.  대한민국과 호주라면, 호주는 8번이죠.  4강에서 가면 만날 수 있죠.

 

문제의 링크입니다.

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

1057번: 토너먼트

이 문제는 공통조상 찾는 문제와 비슷해보이지만, 실제론 더 간단합니다.  공통조상을 찾기 위해서는 트리를 순회해주어야 하지만, 이진트리는 정해진 위치에 해당 노드를 확실하게 찾을 수 있기 때문에 복잡한 트리 순회를 하지 않아도 됩니다.

 

이진수중에 하위비트를 하나씩 제거하면서 같은 상위비트값을 갖게된다면 두 팀이 만나게 됩니다.  그렇게 하기 위해서는 번호를 0부터 매겨야 하므로 숫자를 하나씩 줄여주어야 합니다.  캐나다-대한민국이라고 한다면, 각 번호는 1, 4가 됩니다.  2진수로는 001, 100 으로 최상위비트까지 가기 전까지는 같은 수가 생기지 않으므로 결승전에서 만납니다.  대한민국-호주는 4와 7이 됩니다.  2진수로는 100, 111 로 최상위 비트 전에서 같은 수가 생깁니다.  그래서 4강에서 만나게 됩니다.

 

이런 알고리즘으로 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1057 - Tournament
//    - by Aubrey Choi
//    - created at 2019-07-03
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int n, a, b, c = 0;
  scanf("%d%d%d", &n, &a, &b);
  for(a--,b--;a != b;a>>=1,b>>=1,c++);
  printf("%d\n", c);
}