[BOJ] 15708번: 미네크래프트

https://www.acmicpc.net/problem/15708

일단 관찰을 통해

1. 돌을 건드릴거면 아예 캘 수 있을 때 까지 곡괭이질을 해야하고, 안 건드릴거면 곡괭이질을 하지 않고 넘어가는 것이 이득이다.

2. 왼쪽으로 이동하는 것은 시간적으로 손해이기 때문에 계속 오른쪽으로만 가면 된다.

이 두 가지 성질을 알 수 있습니다.

이제 A개의 돌 까지 내가 이동을 완료했을 때 캘 수 있는 돌의 최대 갯수는 작은 것 부터 합을 구해 T-A*P 이하로 하면서 최대한 많이 합할 수 있는 갯수입니다.

문제의 예시

6 17 1

3 5 2 6 9 1

를 생각해보면, 첫 번째 돌까지 진행했을 경우 17(=17-1*0)이라는 시간을 돌 캐는데 쓸 수 있으므로 최대 1개 캘 수 있고

두 번째 돌까지 보면 16이라는 시간을 돌 캐는데 쓸 수 있으므로 2개,

세 번째 돌에서는 시간 15이므로 3개,

네 번째 돌에서는 시간 14이므로 3개,

.

.

뭐 이런식입니다. 즉 새로이 추가되는 돌을 포함해 정렬된 리스트를 들고 있으면 그 순간에 돌을 몇 개 캘 수 있는지를 알 수 있는데, 이를 리스트로 관리하는 대신 Max Priority Queue로 관리를 한다면 Priority Queue 내의 원소의 합을 들고있음으로 Amortized O(NlgN)에 풀이가 가능함을 알 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/15708.cpp