[Kickstart][2019][Round A] 1. Training

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/00000000000698d6

---

N명의 학생이 있고 이 중 P명의 학생을 선택하려고 한다.

각 학생들은 등급이 있는데 선택하는 학생들의 등급은 모두 같아야한다.

학생에게 1:1 코칭 1시간을 해주면 등급이 1증가한다.

최소의 시간으로 학생들의 등급을 높여 P명의 학생을 선택할 때, 코칭하는데 드는 시간의 최소값은 얼마인가.

---

P명의 학생을 선택할 때, 이를 팀으로 이루기 위해 코칭하는데 드는 최소 시간은 얼마일까.

P명의 학생들 중 가장 높은 등급을 학생들이 모두 가지게 된다면 팀을 이룰 수 있게된다.

즉, (가장 높은 등급 * P) - P명의 등급의 합이 코칭하는데 드는 최소 시간이다.

ex) P = 3, P명의 학생의 등급을 {1,3,6} 이라 할때, 각 학생을 코칭하는데 드는 시간은 {5, 3, 0}이다. 

이는 {6-1, 6-3, 6-6} 과 같고 이 합은 (6-1) + (6-3) + (6-6) = (6+6+6) - (1+3+6) = 6*3 - (1+3+6) 이 된다.

 

먼저 학생들의 등급을 오름차순 정렬하고 부분합을 구한다. 이 부분합으로 P명의 등급의 합을 구할 수 있다.

앞에서부터 탐색하면서 요소의 갯수가 P개인 부분합에서 (가장 높은 등급 * P) - P명의 등급의 합을 구한다. 이들 중 최소값이 정답이 된다.

 

시간복잡도는 오름차순 정렬하는데 가장 오랜 시간이 드니까 O(NlogN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2019/roundA/1.%20Training.cpp