[백준 1057] 토너먼트 (C#, C++) - soo:bak

문제 링크

1057번 - 토너먼트

설명

토너먼트에서 두 참가자가 몇 번째 라운드에서 만나는지 구하는 문제입니다. 두 사람은 서로 만나기 전까지 항상 이긴다고 가정합니다.

접근법

토너먼트에서 한 라운드가 끝나면 참가자 수가 절반으로 줄어들고, 각 참가자의 번호도 새로 매겨집니다. 1번과 2번이 붙어서 승자가 다음 라운드의 1번이 되고, 3번과 4번이 붙어서 승자가 2번이 되는 식입니다.

이 규칙에 따르면 현재 번호가 x인 참가자가 이기면 다음 라운드에서의 번호는 (x+1)/2가 됩니다. 예를 들어 3번이 이기면 다음 라운드에서 2번이 되고, 4번이 이기면 역시 2번이 됩니다.

따라서 두 참가자의 번호를 매 라운드마다 갱신하면서 같아지는 시점을 찾으면 됩니다. 번호가 같아졌다는 것은 그 라운드에서 서로 붙는다는 의미입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var a = int.Parse(parts[1]);
    var b = int.Parse(parts[2]);

    var round = 0;
    while (a != b) {
      a = (a + 1) / 2;
      b = (b + 1) / 2;
      round++;
    }
    Console.WriteLine(round);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, a, b; cin >> n >> a >> b;
  int round = 0;
  while (a != b) {
    a = (a + 1) / 2;
    b = (b + 1) / 2;
    round++;
  }
  cout << round << "\n";

  return 0;
}