[BAEKJOON] 1057번 토너먼트

 

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

1057번: 토너먼트

 

지문이 너무 길어서 읽는 시간이 많이 걸렸던 문제였다.

첫번째 접근방식은 모든조건을 if문을 두어 풀어서 시간초과가 났다,,,

소스코드

#include <vector>
#include <iostream>
using namespace std;

int n, kim, im, cnt;
//홀수 일때 마지막 한명 부전승
//라운드 마다 참가자의 번호를 순서 유지하며, 다시 번호 매김
int main(){
	cin >> n >> kim >> im;
	cnt = 1;
	bool possible = false;
	while (1) {
		if (im - kim == 1 && kim % 2 == 1) {
			possible = true;
			break;
		}
		cnt++;
		if (kim % 2 == 0) kim /= 2;
		else if (kim % 2 == 1) kim = kim / 2 + 1;
		if (im % 2 == 0) im /= 2;
		else if (im % 2 == 1) im = im / 2 + 1;
		
	}
	if (possible) cout << cnt;
	else cout << -1;
}

 

어떻게 간단하게 생각할 방법이 없을까 하는 순간에,, 두개씩 짝지었을때 같은 그룹에만 속하기만 하면 되는데 그러면 (n + 1) / 2가 서로같으면 두 사람은 같은 그룹에 속한다는 것을 깨달았다. 문제 지문 길이에 비해서 간단한 문제였다 ,,,,

 어려울수록 돌아가보자,,!

소스코드

#include <vector>
#include <iostream>
using namespace std;

int n, kim, im, cnt;
//홀수 일때 마지막 한명 부전승
//라운드 마다 참가자의 번호를 순서 유지하며, 다시 번호 매김
int main(){
	cin >> n >> kim >> im;
	while (kim != im) {
		cnt++;
		kim = (kim + 1) / 2;
		im = (im + 1) / 2;
	}
	cout << cnt;
}