토너먼트

문제

언어

  • JavaScript

순서도

  1. N 명의 선수가 매번 경기를 치뤄서 2 명의 선수가 될 때까지 (즉, 남는 선수가 김지민과 임한수가 될 때까지)
  2. 김지민과 임한수를 다음 라운드로 올립니다. (라운드 수를 증가시키고, 김지민과 임한수의 다음 라운드 번호 배정)
  3. 2 번을 반복하다가 김지민과 임한수가 경기를 치루게 되는 라운드를 출력

문제 풀이 step 1

  • N 명이 스타 토너먼트에 참가합니다. 그리고 N 명의 선수들은 1 번 부터 N 번 까지 번호를 배정받습니다. 그러고 난 후에 서로 인접한 번호끼리 스타를 합니다.
  • N 명의 선수들 중에는 김지민과 임한수가 있습니다. 그리고 1 라운드에서의 김지민과 임한수의 선수 번호가 주어졌을 때, 몇 라운드에서 둘이 경기를 하게 되는지 알아내는 문제입니다.
  • 김지민과 임한수 모두 서로 경기를 하기 전까지는 항상 이긴다고 가정합니다.

문제 풀이 step 2

  • 선수들이 서로 경기를 하기 위해서는 번호가 인접해야 합니다.
  • 인접한 번호들에는 1 과 2, 6 과 7, 9 와 10 이 있습니다. 하지만 무조건 인접한다고 해서 경기를 치루진 않습니다.
    • 1 과 2 의 경우는 경기를 치룹니다.
    • 6 과 7 의 경우는 경기를 치루지 않습니다. 왜냐하면 6 은 5 와 경기를 치루고, 7 은 8 과 경기를 치루기 때문입니다.
    • 9 와 10 의 경우는 경기를 치룹니다.
    • 위의 경우들 통해서 어떤 성질을 찾아낼 수 있습니다.
    • 경기를 치루기 위해서는
      • 번호가 작은 선수는 홀수여야 하며,
      • 번호가 큰 선수는 번호가 작은 선수의 번호 + 1 이여야 합니다.
    • 즉, if (번호가 작은 선수 % 2 !== 0 && 번호가 큰 선수 === 번호가 작은 선수 + 1) 과 같은 조건을 얻어낼 수 있습니다.
  • 따라서 위의 조건이 만족하면 김지민과 임한수는 경기를 치루게 되는 것입니다.

문제 풀이 step 3

  • 그리고 어떤 선수가 다음 라운드에서 배정받는 번호는 어떻게 구할까요??
  • 우선 인접한 선수들을 나열해보면, 1 과 2, 3 과 4, 5 와 6 이 있습니다.
    • 1 과 2 가 경기를 해서 1 이 올라간다고 하면, 다음 라운드에서도 1 번을 배정받습니다.
    • 3 과 4 가 경기를 해서 4 가 올라간다고 하면, 다음 라운드에서는 2 번을 배정받습니다.
    • 5 와 6 이 경기를 해서 5 가 올라간다고 하면, 다음 라운드에서는 3 번을 배정받습니다.
    • 이번에도 위의 경우들을 통해서 어떤 성질을 찾아낼 수 있습니다.
    • 어떤 선수가 다음 라운드에서 배정받는 번호는
      • 경기를 치루는 두 선수 중에서 번호가 큰 선수의 번호를 반으로 나눈 값입니다.
    • 즉, parseInt((어떤 선수의 번호 + 1) / 2) 로 구할 수 있습니다.
      • 번호가 작은 선수에 + 1 을 하면 번호가 큰 선수와 같아지기 때문에 그 값에서 나누기 2 를 하면 다음 라운드에서 배정받는 번호가 됩니다.
      • 번호가 큰 선수의 경우 + 1 을 하고 나누기 2 를 하면 소수값이 발생하는 데, 그 소수 값을 날려버리면 다음 라운드에서 배정받는 번호가 됩니다.
      • 소수 값을 날려버리기 위해서 parseInt()를 사용했습니다. 대신에, Math.floor() 를 사용해도 됩니다.

문제 풀이 step 4

  • 위에서 알아낸 정보를 이용해서,
  • 매 라운드마다 김지민과 임한수에게 다음 라운드 번호를 배정하고, 서로 대결하게 될 때 라운드 수를 출력해주면 정답이 됩니다.
  • 문제에서 서로 대결하지 않을 때는 -1 을 출력하라고 했지만, 둘이 서로 대결하기 전까지 무조건 이기면서 올라오기 때문에, 서로 대결하지 않는 경우는 없다고 생각해서 그 경우는 제외했습니다.
  • 추가 설명은 주석에 작성하겠습니다.

소스 코드 1

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	let [n, jimin, hansoo] = input[0].split(" ").map(Number);

	// 김지민과 임한수의 번호를 오름 차순으로 변경
	// (번호가 작은 선수와 큰 선수가 명확히 구분해야 로직이 간단해서져서 넣은 코드입니다.)
	if (jimin > hansoo) [jimin, hansoo] = [hansoo, jimin];

	let round = 1;
	while (n > 1) {
		// 번호가 작은 선수는 홀수이고, 번호가 큰 선수는 번호가 작은 선수의 번호 + 1 이면 경기
		if (jimin % 2 !== 0 && jimin + 1 === hansoo) break;

		// 김지민과 임한수에게 다음 라운드 번호를 배정
		jimin = parseInt((jimin + 1) / 2);
		hansoo = parseInt((hansoo + 1) / 2);

		round += 1;
		n = parseInt((n + 1) / 2);
	}

	// 라운드 수 출력
	return round;
};

console.log(solution(input));