Study/PS(Algorithm)
[C++] 백준 BOJ 1057 토너먼트
노랑펭귄
2019. 1. 9. 17:48
문제링크 : https://noj.am/1057
문제의 조건에서 지민과 한수가 둘이 만나기 전까지는 무조건 이긴다고 하였다.
따라서 문제에서 나온 조건대로 하면 '만약 서로 대결하지 않을 때는 -1을 출력한다.'은 절대로 나올 수 없기 때문에 무시해도 된다.
두 사람이 만날 수 있는 조건은 A와 B가 각각 2n-1과 2n 이어야 하는 조건이다.
계산을 편하게 하기 위해서 그냥 A, B를 작은 순서대로 정렬하고 A가 홀수이고 A-B의 차가 1이면 정답으로 출력하도록 했다.
두 사람이 각 라운드에서 만나지 못한다면 div( ) 함수를 통하여 입력값을 절반으로 나누어주면서 정답을 찾아가면 된다.
절반씩 계속 나누기 때문에 최악의 경우에도 O(logN)의 시간복잡도를 보일 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | // BOJ_1057 토너먼트 #include <iostream> using namespace std; // 입력 값을 절반으로 나누고 // 홀수면 +1을 더해준 값으로 반환 int div(int n) { return n % 2 ? n / 2 + 1 : n / 2; } // 작은 숫자가 a, 큰 숫자가 b가 되도록 정렬(스왑) int sort(int &a, int &b) { if (a > b) { int temp = a; a = b; b = temp; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int num; int person1, person2; cin >> num >> person1 >> person2; sort(person1, person2); int round = 0; while (true) { round++; // person1이 홀수이고 person2와의 차가 1이면 if (person1 % 2 && person2 - person1 == 1) break; // 다음 라운드로 진출 시 숫자를 절반으로 나눔 person1 = div(person1); person2 = div(person2); } cout << round; return 0; } | cs |
더 쉬운 방법으로는 각 숫자를 1씩 빼줘서 1~N 범위의 숫자를 0~N 범위로 만든 다음에 2n과 2n+1일때의 case를 찾으면 더 간단하게 풀린다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | // BOJ_1057 토너먼트 #include <iostream> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int num; int person1, person2; cin >> num >> person1 >> person2; // 1~N 범위를 0~N-1로 변환 person1--; person2--; int round = 0; // 두 수가 각각 2n과 2n+1이면 정답 // 이때, 2로 나눴을 때 두 수가 같아지므로 탈출 조건으로 설정 while(person1 != person2){ round++; person1 >>= 1; person2 >>= 1; } cout << round; return 0; } | cs |