[백준 BOJ] 1057 토너먼트

1057_토너먼트

링크

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

 

풀이

 

토너먼트이기 때문에 8과 9를 2로 나누면 동일한 4를 갖는 성질을 이용해서 풀 수 있습니다.

만약 1, 2, 3  3명이 경기를 할 때, n인 3+1을 2로 나누면 부전승 포함 2명이 남고, 1+1과 2+1을 2로 나누면 둘의 승자는 1이라는, 3+1을 2로 나누면 2라는 번호가 부여됩니다.

 

저 상황에서 1과 2가 김지민과 임한수라면 둘 다 1을 더하고 2로 나눴을 때, 같은 값을 가진다면 그때 상대와 붙는 것입니다.

 

그래서 결론은 1을 더하고 2로 나누는 방식으로 n(인원수), 김지민의 번호, 임한수의 번호를 제어해서 언제 대결하는지 파악하면 됩니다.

 

마지막에 대결하지 않는 경우가 나오는데, 둘 다 서로 대결할 때까지 모든 경기를 이기기 때문에 고려하지 않아도 됩니다.

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

//1057_토너먼트 #include <cstdio> using namespace std;   int n, a, b, i;   int main() {     scanf("%d %d %d", &n, &a, &b);       while (++i) {         n++, a++, b++;                  if (a / 2 == b / 2) {             printf("%d\n", i);             break;         }           n /= 2, a /= 2, b /= 2;     }       return 0; }

cs