Team - BOI 2004

BOJ - 굉장한 학생(Team)

한 학생이 3개의 시험에 대해 A, B, C 의 순위를 가지고 있다.

이 때, 어떠한 학생들 중에서도 A' < A && B' < B && C' < C 인 (A',B',C')의 순위를 가진 학생이 존재하지 않으면, (A,B,C)의 순위를 가진 학생을 굉장하다 한다.

N명의 학생 중, 굉장한 학생이 몇 명인지 알아내야 한다.

1. Naive - O(N^2)

한 학생 i를 잡고, 나머지 학생들 중 i보다 대단한 학생이 있는지 아닌지를 O(N)에 판별한다.

이 과정을 모든 학생에 적용, 총 O(N^2)에 문제를 해결 할 수 있다. Naive는 매우 직관적이다.

KOI 덩치 

위 문제는 '굉장한 학생' 문제에서의 인자가 하나 적은 문제이다. 이러한 경우, 우리는 첫 인자를 기준으로 정렬하여 나머지 인자로만 비교하는 방법을 사용할 수 있다.

이 문제도, 첫 번째 시험에 대한 결과를 기준으로 정렬하고 나면, 정렬의 우선순위가 낮은 학생은 그 앞의 학생보다 대단할 수 없다는 것이 보장된다.

정렬하면, 한 학생에 대해 나머지 두 개의 인자에서 대단한 학생이 존재하는지를 찾아내는 방법을 만드는 문제로 바뀌게 된다.

나머지 두 개의 인자에 대해서는 구간 관리를 통해 O(lg N)에 판단할 수 있다.

2. Indexed Tree - O(NlgN)

시험을 순서대로 각각 A,B,C 시험이라고 하자. 처음에 A 시험의 순위대로 정렬한다.

이후 B 시험의 순위를 인덱스로 하는 노드를 만들고, B 시험의 1위 노드를 B1, 2위를 B2, 와 같이 명명한다.

A 시험의 순위가 높은 학생(1,2, ... , N)부터 다음 연산을 수행한다.

1 - 현재 학생의 B 시험의 순위를 b, C 시험의 순위를 c라고 하고, Bb의 노드 값을 c로 한다.

2 - B1~B(b-1) 까지의 노드의 최솟값을 min_c라고 하자.

3 - c가 min_c보다 클경우 (수가 클 경우, 순위가 낮을 경우) 현재 학생보다 대단한 학생이 존재한다는 것, 아니면 현재 학생은 굉장한 것이다.

이유는 다음과 같다

1. 현재 학생 이전에 처리된 학생은 현재 학생보다 A의 순위가 높다 (수는 작다)

2. B1~B(b-1) 까지의 노드에 값이 있다면, 그 값을 B 시험의 순위로 하는 학생은 현재 학생보다 B 시험의 순위가 높다.

3. 구간의 노드 값 중 최솟값, min_c가 c보다 순위가 높다면, min_c에 해당하는 값을 C 시험의 순위로 하는 학생은 현 학생보다 C 시험의 순위가 높으며, 1, 2로 인해 A와 B 시험의 순위도 더 높다.

우리는 이제 B1~B(b-1) 노드들 중 최솟값을 찾는 자료구조를 구현하기만 하면 된다.

이는 Indexed Tree (다른 자료구조도 상관 없다) 를 이용해 쿼리당 O(lg N)에 처리 가능하게 할 수 있고, 학생 수만큼 반복하므로 총 시간 복잡도는 O(NlgN) 이다.

꽤 좋은 문제, 많은 사람들이 아는 익숙한 문제에서 인자를 늘려 차원을 높였다.

문제 상황을 파악하고 나면 쉽게 접근할 수 있다.