[CodeJam][2017][Round 1C] A. Ample Syrup

문제 : https://code.google.com/codejam/contest/3274486/dashboard#s=p0&a=0

---

그리디로 풀었다.

학창 시절 때의 수학시간을 생각해보면 소스가 뿌려진 총 면적에서 높이는 각 팬케이크의 높이를 다 더한 값이지만 원의 너비는 가장 큰 팬케이크의 너비와 같다. 

따라서, 너비를 기준으로 탐색한다. -> 너비를 기준으로 팬케이크를 오름차순 정렬한다.

앞에서 부터 팬케이크를 탐색하면서 팬케이크의 높이를 구한다. K개를 만족한다면 현재 탐색중인 팬케이크의 너비 + 이때까지 구한 팬케이크 높이가 정답이 될 수 있는 경우이다. 현재 탐색중인 팬케이크의 너비는 너비를 기준으로 오름차순 정렬했으므로 이때까지 탐색한 팬케이크의 너비 중 최대값임을 보장한다. 또한 오름차순 정렬했으므로 이때까지 탐색한 팬케이크의 너비는 현재 탐색중인 팬케이크의 너비보다 작거나 같음을 보장하므로 탐색중인 팬케이크 위에 차례대로 쌓일 수 있음을 보장한다.

탐색하면서 구한 각 팬케이크의 높이는 우선순위 큐(작은 것이 우선순위가 높음)에 저장한다.

계속 탐색하면서 K+1개의 팬케이크가 포함된다면 높이를 저장한 우선순위 큐에서 가장 작은 높이를 제외한다.

N개의 팬케이크를 탐색하면서 구한 정답이 될 수 있는 경우의 소스 면적 중 최대값이 정답이 된다.

시간복잡도는 O(NlogN).

---

소스코드 : https://gist.github.com/fpdjsns/dc60fba5843c2d305c9c2ff5e247bb73