https://www.acmicpc.net/problem/31783
문제요약
- 1 ~ N까지 높이가 있고, 내려가는 계단이 있음(N 30만, 높이 10^9, 단조감소)
- 계단마다 보물상자의 점수, 내구도가 있음
- 보물을 얻으려면 현재 보물이 놓여진 계단의 높이 + 내구도 이상인 앞선 계단에서 내려와야함
- 얻을 수 있는 최대 점수 구하기
접근법
- 보물을 얻을 수 있고, 최대 점수를 얻고 싶으면
- 앞선 계단에서
- 높이가 일정 값 이상인 것들 중
- 얻은 점수가 최대인 곳에서 내려와야함
- 계단이 단조 감소이므로 일정 값 이상인 지점을 찾고 그 앞의 범위에서 뭔가 하면 됨
- 최대인 것을 알면 되니까 구간트리를 사용해도 됨 (구현은 이렇게 했음)
- 그런데 구간트리를 사용하기 전에 조금더 생각해보면 특정 계단까지 내려왔을때 최대값을 유지하면 구간트리가 필요없음
- 즉 특정 계단까지 올때 특정계단의 보물을 얻어서 점수를 내던가
- 바로 전 계단에서 그냥 내려올 수 있음
- 둘 중에 큰 값이 특정 계단까지 올 때의 최대 점수임
- 그리고 이 값은 계속 커짐
- 즉 높이는 계속 작아지고, 점수는 계속 커지기 때문에 앞선 계단에서 최소 높이만 잘 찾으면 됨
newbieski