[백준/C++] 1057번. 토너먼트

문제

1057번: 토너먼트

---

1. 첫 번째 풀이 (마지막 풀이)

사고 과정

- 일단 간단하게 구현으로 시작해보자.

- 1부터 시작, i(홀수)와 i+1(짝수)를 서로 대진시킨다.

- 이들은 다음에 어떤 번호를 받게 될까?

- 일반적인 경우, 짝수 / 2의 번호를 받게 된다. (1, 2)는 1, (3, 4)는 2, (5, 6)은 3...

- 홀수는? 홀수 / 2 + 1 번호를 받게 된다.

- 경쟁자가 홀수인 경우엔 어떻게 되지? 25명이면 24는 12, 25는 13을 받는다. 문제없을 듯.

- 끝까지 안 만날 경우는 없으니 그냥 둘이 같을 때까지 반복하면 되지 않을까? 재귀로 해보자.

 

1. N, k, l을 선언, 입력

2. 두 수를 받아 짝수면 / 2, 홀수면 / 2 + 1하는 함수를 작성

3. Base Case는 k == l, 1을 리턴.

4. 이외엔 1 + 재귀함수 호출, 리턴.

 

코드

#include <cstdio>

int BattleNumber(int k, int l) {
	if (k == l) {
		return 0;
	}

	k = (k % 2 == 0) ? k / 2 : k / 2 + 1;
	l = (l % 2 == 0) ? l / 2 : l / 2 + 1;

	return 1 + BattleNumber(k, l);
}

int main() {
	int n, k, l;
	scanf("%d %d %d", &n, &k, &l);
	printf("%d", BattleNumber(k, l));
}

 

결과

일단 성공.

---

개선

사고 과정

- 반복 없이 풀 수 있을까? (ex. log 사용 등)하고 생각해봤는데, 그런 경우 부전승도 따로 고려해야 하고, 뭣보다 판 수를 결정할 마땅한 근거를 찾을 수 없었다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/37543058

wjddn041007님의 코드. 순위 자체는 14위로 낮아보이지만, 로직은 똑같고 쓸데없는 코드 줄이기가 없어 가져왔다.

 

내 코드와 비교

- 우선 for문으로 구현하셨다.

- 홀수 / 짝수를 나누는 대신, 각 수에 1씩 더하고 2로 나눴다. 조건문 없이 한 번에 다음 번호를 찾을 수 있었다.

- 판수는 c로 카운트 하셨다.

- for의 조건문에서, / 2끼리 비교했다.

---

강평

다음 번호를 찾는 법만 알아내면 쉽게 풀리는 문제. 재귀는 재귀대로, 반복문은 반복문대로 각각 장점을 갖는다. 이외에도 / 대신 >> 연산을 사용할 수도 있다.