[BOJ] 2515번: 전시장

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

우선 그림을 높이 순으로 정렬합니다. 그리고 D[i]를 pic[0~i]를 전시할 때 최댓값(단 i번째 그림은 반드시 보여짐)이라고 잡는다면, D[i]는 pic[i]-S 이하의 높이를 가진 그림 pic[0], pic[1], ..., pic[k]에 대해 D[i] = max(D[0], D[1], ... , D[k]) + pic[i]의 높이 입니다.

max(D[0], D[1], ... , D[k])를 각 i에 대해 매번 구하게 될 경우 O(N^2)이지만, max 값을 누적시켜서 계속 가져가면 O(N)으로 해결이 가능합니다. 그러므로 시간복잡도는 최초의 정렬때 O(NlgN), 이후 DP에서 O(N)이 되어 O(NlgN)이 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/2515.cpp