어느 도시에서 축구경기 토너먼트를 하기로 했다. 토너먼트 참가 팀은 총 100 팀으로, 게임 주최자인 당신은 100개의 팀이 토너먼트 기간동안 벌일 총 경기수를 헤야려야 한다. 그 수는 얼마나 될까?
답은 두 가지 방법으로 풀 수 있다. 하나는 방법은 간단한데 시간이 많이 들고, 다른 하나는 조금 생각해야 하지만 금방 답을 얻을 수 있다. (전자가 무식하게 풀었다면, 후자는 위트를 쓴 풀이다.)
답
1. 주먹구구식 풀이
긴말 필요없다. 그냥 다 그려보고 하나하나 다 세서 죄다 더한다.
답 : 99번
사실, 그림을 그리지 않고도 그냥 수열로서 구할 수 도 있다. 토너먼트이기 때문에 총 팀 숫자에서 2를 나눈 숫자를 계속 적어나간다. 만약 그 와중에 홀수가 나오면, 부전승을 생각하여 1을 빼고 2로 나눈다. 마지막에 1까지 적었으면 이제 다 더한다. 만약 처음 100팀이었다면, 50 -> 25 -> 12 -> 6 -> 3 -> 2 -> 1. 따라서 다 더하면 99다.
허나, 이런 식이라면, 1000팀, 10000팀이 올 땐 감당할 수가 없다. 계산기라도 두드릴 것인가? (물론 알고리즘을 잘 짜는 컴퓨터 박사들은 그래도 된다. 암.) 이제 순식간에 답이 나오는 생각을 해보자.
2. 센스만점 풀이
총 경기 수에만 집착하다보면 쉬운 풀이를 놓치기 쉽상이다. 이 문제의 센스발휘는 총 경기 수 대신 그와 일치하는 어떤 값를 생각하는 것이다. 매 경기마다 한 팀의 탈락자가 나오므로, 총 경기 수와 총 패배 팀의 수는 같다. (한 경기마다 한 탈락 팀을 연결지을 수 있으므로, 함수적으로 보았을 때, 일대일 대응으로 간주해도 좋다.) 그런데, 총 패배 팀은 너무나 쉽게 구할 수 있다. 챔피언의 자리에 오르는 것은 단 한 팀이므로 전체 팀 숫자에서 1을 뺀 99가 답이 된다.
