[백준 BOJ] 1057번 토너먼트 (C++/cpp)

문제 설명

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

1057번: 토너먼트

 

접근 방법 - 브루트포스 알고리즘을 응용한 문제

백준의 1057번 문제는 브루트포스 알고리즘을 이용하여 해결해야 하는 연산 문제이다.

해당 문제는, 문제에 있는 김지민과 임한수가 몇 라운드에서 대결하게 되는지를 구하여 출력해야 하는 문제이다.

필자는 이 문제의 원리를 찾기 위해 아래처럼 생각을 하였다.

1라운드의 경우
┌┐
1 2 ...

2라운드의 경우
  ┌─┐
┌┐ ┌┐
1 2 3 4  ...

3라운드의 경우
     ┌───┐
  ┌─┐    ┌─┐  
┌┐ ┌┐ ┌┐ ┌┐
1 2 3 4 5 6 7 8  ...

...

이렇게 보면, 토너먼트 라운드 간의 참가자 번호 간격이 2, 4, 8, 16, ... 순으로 늘어나고 있음을 알 수 있다.

필자는 이 규칙을 이용하여 코드를 작성하였으니, 이를 염두에 두면 문제 해결에 많은 도움이 될 것이다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 참가자의 수(n)와 김지민과 임한수의 번호(a, b)를 순차적으로 입력받는다.

 

2) 2의 거듭제곱이면서 입력받은 n보다 크거나 같은 최솟값을 찾아, 이 숫자를 n으로 갱신한다.

(토너먼트는 위 설명처럼 2의 거듭제곱 수로 인원이 나누어지며 진행되기 때문에, 이 숫자를 기점으로 연산을 진행해야 한다.)

 

3) 라운드를 카운팅 할 변수 cnt를 0으로 초기화하여 선언한다.

 

4) 반복문을 실행하여, 2의 거듭제곱 순으로 제어 변수(i)의 값을 늘려가며 아래의 연산을 수행한다.

- cnt에 1을 더하여 라운드 수를 올린다.
- 다른 반복문을 통해, 해당 라운드에 있어 진행되는 경기를 하나씩 탐색한다.

(예를 들어, 2라운드의 경우엔 1~4 / 5~8 / 9~12 / ... 를 각각 탐색하도록 한다.)

만일 한 묶음에 김지민과 임한수의 번호가 둘 다 존재한다면, 현재 cnt의 값을 출력한 뒤 즉시 실행 종료한다.

 

5) 4)에서 결과 출력이 완료되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 1057번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, a, b;
	cin >> n >> a >> b;
	for (int i = 2; 1; i *= 2) {
		if (i >= n) {
			n = i;	break;
		}
	}
	
	int cnt = 0;
	for (int i = 2; i <= n; i *= 2) {
		cnt++;
		for (int j = i; j <= n; j += i) {
			if (a > j - i && a <= j && b > j - i && b <= j) {
				cout << cnt << endl;
				return 0;
			}
		}
	}
}

 

제출 결과

(2022.07.26 백준 1057번 문제 제출 결과)

결괏값이 -1로 나오는 경우는 없었다 카더라