문제

• 
• 시간 제한: 2초
• 메모리 제한: 256MB

Problem Analysis

마지막에 풀 문제부터 시작해서 거꾸로 조사하면, 매 단계에서 풀 수 있는 최적의 문제를 선택할 수 있다. 즉, Greedy 하게 풀면 된다.

Algorithm

마지막 시간부터, 시간 0까지 단위 시간별로 풀 문제를 다음에 따라 선택한다.
1. 현재 시간에 풀 수 있는 문제를 선택지에 추가한다.
2. 누적된 선택지 중에서 최대의 보상을 선택한다.

Data Structure

• problems[]: 문제들을 마감 기준으로 내림차순으로 저장
• pq: 현재 시간에 풀 수 있는 문제들을 보상을 기준으로 내림차순으로 priority_queue에 저장

결과

Other

시간 복잡도는 O(NlogN)이다.