Jonyo Programming

[BOJ 2517(P4)리뷰] 이 문제는 Inversion Count 알고리즘을 이용하여 해결할 수 있다. 문제를 잘 읽어보자. 각각의 선수들은 달리기를 하고 있는데, 자신보다 앞에 있는 선수보다 실력이 좋으면 그 선수를 따라잡을 수 있다고 한다. 이 때 각각의 선수들의 최선의 등수를 구해야 한다. 즉, 문제를 쉽게 풀자면 각각의 선수마다 자신의 앞에있는 선수 중 자신보다 능력치가 낮은 선수가 몇명인지 구하여 자신이 그 선수들을 따라잡았을 때의 최종등수가 몇등이냐를 구해야 하는 문제이다. 가장 쉬운 풀이로는 각각의 선수마다 앞의 있는 선수들을 탐색하는 O(N^2)풀이를 떠올리겠지만 이 풀이로는 시간초과를 맞게된다. 더 효율적인 알고리즘이 필요하다. 이 때 사용한 방법이 inversion count다. 머..