레벨업 일지

문제 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 풀이 현재 위치 i 에서 0..i-1 중에 자신의 실력보다 낮은 개수를 센 다음, 차를 구하는 문제. 분할 정복으로 정렬해서 O(N log N) 풀이하였다. 알고리즘은 다음과 같다. 1. 분할 정복 소트 기법을 사용한다. 2. 두 배열을 병합할때 RIght 배열 원소를 삽입 할때 자기 Left 배열에서 현재숫자보다 낮은 개수를 누적합한다. 3. 자기 자신의 인덱스 - 자신 실력보다 낮은..