💡문제 분석 요약

오늘부터 N+1일째 되는 날 퇴사하기 위해서 남은 N일 동안 최대한 많은 상담하려고 함.

각각의 상담은

• 상담을 완료하는데 걸리는 기간 $T_i$
• 상담을 했을 때 받을 수 있는 금액 $P_i$

<aside> 🔖

예제) N = 7일 때 상담 일정표

1일에 잡혀있는 상담은 총 3일이 걸리고, 받을 수 있는 금액은 10

5일에 잡혀있는 상담은 총 2일이 걸리고, 받을 수 있는 금액 15

또한, 1일에 상담을 하게 되면 2, 3일에는 상담을 할 수 없음.

2일에 상담을 하게 되면, 3, 4, 5, 6일에는 상담을 할 수 없음.

또한 N + 1일에는 회사에 없기 때문에 6, 7일 상담도 불가능

→ 퇴사 전에 할 수 있는 상담의 최대 이익은 1, 4, 5일에 상담을 진행해서 얻는 10 + 20 + 15 = 45

</aside>

⇒ 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램

입력

• 첫째 줄 : N
  • 1 ≤ N ≤ 1,500,000
• 둘째 줄 ~ N개 : $T_i$, $P_i$
  • 공백으로 구분
  • 1일부터 N일까지 순서대로
  • 1 ≤ $T_i$ ≤ 50
  • 1 ≤ $P_i$ ≤ 1,000

출력

백준이가 얻을 수 있는 최대 이익

• 예제

<aside> 📎 https://www.acmicpc.net/problem/15486

</aside>