[문제적 남자] 말 25마리 중 가장 빠른 3마리를 찾기위해 수행해야 할 최소 경기는?

1. Question

컴공에게는 익숙해보이는 문제.

2. Approach

컴퓨터 공학의 알고리즘 중, 외부 정렬 (External Sort)이 유사한 환경으로 보인다.

먼저, 말이 겹치지 않게 5마리씩 25마리가 경주를 한다.

Round1	Round2	Round3	Round4	Round5
1	1	1	1	1
2	2	2	2	2
3	3	3	3	3
4	4	4	4	4
5	5	5	5	5

이제 각 라운드의 1등끼리 경주를 한다. 여기서 1등한 말이 전체 1등이다.

이제 1등한 말을 쫓아낸다. Round1의 1등말이 전체 1등이라고 하자.

Round1	Round2	Round3	Round4	Round5
2	1	1	1	1
3	2	2	2	2
4	3	3	3	3
5	4	4	4	4
	5	5	5	5

이제 다시 각 라운드에서 가장 순위가 높은 말끼리 경주를 한다. 여기서 1등한 말이 전체 2등이다.

이렇게 전체 3등까지 뽑아 낼 수 있다. 따라서 총 8번의 경주를 하면 가장 빠른말 3마리를 알아낼 수 있다.

끝.

는 틀림. 역시 문제적남자.

생각해보니 외부 정렬은 모든 원소를 정렬하기를 원하는거지만 이 문제는 가장 빠른 3마리만 알아내면 된다.

따라서 5번의 경주후에 1등을 골라내기 위해 각 라운드의 1등끼리 다시 한 번 경주를 하고, 라운드 수 별로 등수가 매겨졌다고 하자 (라운드 1의 말이 1등, 라운드 5의 말이 꼴등). 

Round1	Round2	Round3	Round4	Round5
1	1	1	1	1
2	2	2	2	2
3	3	3	3	3
4	4	4	4	4
5	5	5	5	5

그러면 라운드 4, 5의 1등말은 잘해봐야 전체에서 4, 5등이라는 뜻이다. 다른 라운드 4, 5의 말들은 이들보다 느리기 때문에 아에 볼 필요가 없다.

또한, 라운드 1의 4, 5등, 라운드 2의 3~5등, 라운드 3의 2~5등 역시 잘해봐야 4등 이하니까 볼 필요가 없다.

Round1	Round2	Round3	Round4	Round5
1	1	1	1	1
2	2	2	2	2
3	3	3	3	3
4	4	4	4	4
5	5	5	5	5

위에 표에서 볼 수 있는 남은 말의 수가 5마리 이므로 한번의 경주만에 순위를 매길 수 있다. 따라서 필요한 최소 경기수는 7경기이다.