백준 2517번 달리기

< 백준 2517번 달리기 - 마포 코딩박 >

사용한 알고리즘: Fenwick tree


 선수들이 현재 달리고 있는 순서 대로, 선수들의 능력치가 주어집니다. 능력이 큰 선수는 자신보다 앞에 있는 능력이 작은 선수를 앞지를 가능성이 있습니다. 이때 각 선수의 가능한 최대 등수를 구하는 문제였습니다.
 사실 " 각 선수의 가능한 최대 등수 = 들어온 순서 - 자신 앞에 있는 능력 작은 선수 수 " 입니다.

문제풀이는 다음과 같습니다.
(1) (코드: 12~16, 51~59)
 선수의 능력이 1~10^9 이므로 이를 그대로 배열로 받을 수 없습니다. ( 터집니다.... )
 하지만 선수의 수가 3~5*10^5 밖에 안되므로, 선수들의 능력치를 최대 5*10^5 로 압축했습니다. 즉 선수 능력치가 극단적으로 10, 222222, 99999999999 인 경우나 1, 2, 3 인 경우나 대소는 같습니다.
 따라서 저는 능력이 큰 순으로 정렬을 시켜, 가장 큰 값을 5*10^5 부터 차례로 바꾸어 주며 능력을 압축했습니다. ( 선수 수가 최대 5*10^5 입니다. )

(2) (코드: 17~39, 60~68)
 들어온 순으로 다시 정렬 시켰습니다. 이후 빨리 들어온 선수부터 보면서 등수를 매겼습니다.
 i 번째 선수의 가능한 최대 등수는 i - ( 자신 앞 작은 능력 선수 수 ) 입니다.
 i 번째 선수앞에 있는 자신보다 작은 능력의 선수 수를 fenwick tree 로 계산해주었습니다.