겹치지 않는 예약의 최대 혜택

이전 항목 번호 대신 이전 시각에 연결해요

앞 DP는 한 칸·두 칸 전의 답을 썼어요. 이번에는 예약마다 길이가 달라 이전 상태를 해당 예약의 시작 시각에서 읽어요. jobs의 한 행 {start,end,profit}은 start에 시작해 end 직전에 끝나는 예약과 혜택이에요.

예를 들어 [0,2) 예약은 시각 2에 끝나므로 [2,4)와 이어 쓸 수 있어요. [1,3)과는 시간이 겹쳐요. 정렬·이진탐색을 가정하지 않고 작은 정수 시각을 0부터 읽어도 돼요.

현재 시각까지 끝난 최댓값을 유지해요

best[t]를 ‘시각 t까지 끝나는 예약들로 얻는 최대 혜택’으로 정해요. 시각 t에 예약을 끝내지 않는 경우에는 best[t−1]을 유지해요. 시각 t에 어떤 예약을 끝내면 그 예약 시작 시각까지의 답에 혜택을 더해요.

예약 {0,2,4}와 {2,4,7}을 이어 고르는 예예요.

같은 끝 시각의 예약이 여러 개면 전부 함께 더할까요? 서로 겹칠 수 있으므로 각각 마지막 예약인 후보를 비교해요. 반복에서 한 행을 for (vector<int> job : jobs)로 읽으면 job[0]·[1]·[2]가 시작·끝·혜택이에요.

직접 풀어봐요

jobs의 각 예약은 {start,end,profit}이에요. 서로 시간이 겹치지 않는 예약들을 골라 혜택 합의 최댓값을 반환해요. end와 다음 start가 같으면 이어 선택할 수 있어요. 같은 내용의 예약도 다른 항목이지만 시간이 겹치면 둘을 함께 고를 수 없어요. 아무 예약도 안 고를 수 있어요.

예약 수는 016, start는 049, end는 start+150, profit은 01000이에요. 실행용 입력은 첫 줄 예약 수 n, 다음 n줄에 start end profit이에요. 출력은 반환값이에요. 하네스가 입출력을 처리해요.

예시 1: jobs={{0,2,5},{2,4,6},{1,4,15}} → 15. 앞 두 개 합 11보다 마지막 예약 하나의 15가 커요. 예시 2: jobs={{0,3,8},{1,2,10},{2,4,7}} → 17. 끝과 시작이 맞닿은 두 예약을 이어 17을 얻어요.

3
0 2 5
2 4 6
1 4 15

15

3
0 3 8
1 2 10
2 4 7

17