[BOJ] 백준 #1057. 토너먼트 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/1057

• 알고리즘 분류: 수학
• 난이도: Silver Ⅲ

💬 풀이

매 라운드마다 바뀌는 참가자들의 번호를 이용해서 풀 수 있다.
예를 들면, 예제입력1에서 kim: 8→4→2→1→1, lim: 9→5→3→2→1이다.
즉 어떤 라운드에서 번호가 n이라면 다음 라운드에서 번호는 (n+1)/2다.
또한 두 사람의 번호 차가 1이고, 작은 사람의 번호는 홀수 (=큰 사람의 번호는 짝수)일 때 경기에서 만나게 된다.

아 그리고 조건 마지막에 ‘만약 서로 대결하지 않을 때는 -1을 출력한다’고 되어 있는데, 처음에 이거를 생각 안 하고 풀었는데 맞았다길래 뭐지?했는데 생각해보니까 그런 경우는 발생하지 않는다 ….ㅋ 끝까지 서로 대결하지 않는 경우는 없다.

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int N, kim, lim;
	cin >> N >> kim >> lim;

	int round = 1;
	int survivor_n = N;
	while (survivor_n != 1) {
		if ((abs(kim - lim) == 1) && (min(kim, lim) % 2 == 1)) {
			// 둘이 번호가 1차이 나고,
			// 번호 작은애가 홀수, 큰애가 짝수면 => 대결
			break;
		}

		// 다음 라운드 번호 지정, 다음 라운드 생존자 수
		round++;
		kim = (kim + 1) / 2;
		lim = (lim + 1) / 2;
		survivor_n = (survivor_n + 1) / 2;
	}
	
	cout << round;

	return 0;
}